グラフがバタフライかどうかをチェック
5つの頂点と e 本の辺から成る無向グラフが与えられたとき、そのグラフがバタフライかどうかを判定してください。
バタフライグラフとは、5つのノードを持ち、中心となるノードが4つのノードと繋がっている形のグラフです。中心ノードはまず2つのノードと接続され、それら2つのノード同士も互いに繋がっています。一方で、もう2つのノードも中心ノードに繋がっており、それらも同様にお互いが繋がっています。
入力
最初の行には整数 e (1 ≤ e ≤ 20) が1つ与えられます。
続く e 行には、各行で整数のペア v1, v2 (1 ≤ v1, v2 ≤ 5) が与えられます。これは頂点 v1 と頂点 v2 が接続されていることを示します。
出力
グラフがバタフライであれば Yes を、そうでなければ No を出力してください。
例
Input | Output |
|---|---|
6 1 4 1 3 3 4 4 2 4 5 2 5 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB