F - ループを探せ
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
頂点数および辺数がともに 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_i と y_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