CODE FESTIVAL 2014チーム対抗早解きリレー

F - ループを探せ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

頂点数および辺数がともに n であるような連結な無向グラフは、ループをちょうど 1 つだけ含むことが知られています。


このようなグラフが与えられるので、グラフに含まれるループの長さを求めて下さい。


入力

入力は以下の形式で与えられる。

n
x_1 y_1
...
x_n y_n
  • 1 行目には、グラフの頂点数を表す整数 n (3 \leq n \leq 100{,}000) が与えられる。
  • 続く n 行には、グラフの辺の情報が与えられる。
  • それぞれの頂点には 1 から n までの番号が振られており、x_i, y_i (1 \leq x_i,y_i \leq n) は、i 番目の辺によって 2 つの頂点 x_iy_i がつながっていることを表す。
  • 与えられるグラフは連結であり、自己辺や多重辺は含まれないことが保証される。

出力

グラフに含まれるループの長さを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。


入力例1

4
1 2
2 3
3 1
1 4

出力例1

3

入力例2

4
1 2
2 3
3 4
4 1

出力例2

4

Submit提出する