← 返回题目列表

AtCoder · code_festival_relay_f

F. 找到循环

中文机器翻译题面 查看原题

問題文

顶点数和边数均为 连通无向图使得 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