Network Cycle

The information network of the campus consists of nodes and direct connections between some pairs of the nodes. The network is connected which means that using one or more direct connections a signal can travel between any two nodes of the network in either direction. The network contains a cycle.
A cycle is a sequence of at least three nodes n₁, n₂, ..., n_k which also satifies the condition: There is a direct connection between the node n_k and the node n₁ and also there is a direct connection between the node n_i and the node n_{i − 1}, for each 1 < i ≤ k.

     

Image 1. Example of network schemes. The length of the cycle in case a), b), c) is 3, 4, 15, respectively.

The task

You are given the scheme of direct connections in the network. Find the length of the cycle in the network.

---

Input

The first input line contains one integer N, it is the number of nodes in the network. The nodes are labeled by integers 0, 1, ..., N−1. Next, there are N text lines, each describes one direct connection. The line contains the labels of two directly connected nodes, the labels are separated by space.
The order of connections in the input is arbitrary.
It holds, 1 ≤ N ≤ 10⁶.

Output

The output contains one text line with one integer representing the length of the cycle in the network. It is guaranteed that the network contains exactly one cycle in all presented cases.

Example 1

Input

5
0 1
1 3
3 4
2 1
2 3

Output

3

The data of Example 1 are depicted in Image 1a).

Example 2

Input

9
1 2
3 4
6 7
5 6
4 8
3 6
0 2
2 4
4 7

Output

4

The data of Example 2 are depicted in Image 1b).

Example 3

Input

19
0 5
5 10
10 14
1 6
11 15
8 13
4 9
9 18
1 2
2 3
3 4
6 7
7 8
10 11
11 12
12 13
15 16
16 17
17 18

Output

15

The data of Example 3 are depicted in Image 1c).

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set