Consider ~n~ strings with rings at both ends. An integer is attached to each ring such that the integers, say ~a~ and ~b~ which we denote by ~[a, b]~, attached to the both ends of a string are different. These pairs of integers identify the strings.

Two strings ~[a, b]~ and ~[c, d]~ can be connected if one of ~a, b~ is equal to one of ~c, d~, by tieing them together at the rings with the same number. The result is called a chain. For example, a chain ~[1, 3, 4]~ is obtained by connecting two strings ~[1, 3]~ and ~[3, 4]~.

Similarly, a string and a chain, or two chains can be connected together at the rings with the same integer. For example, a chain ~[1, 3, 4]~ and a string ~[5, 1]~ can be connected to produce a chain ~[5, 1, 3, 4]~. From two chains ~[1, 3, 4]~ and ~[2, 3, 5]~, a form looking like a cross (call it ~\alpha~ for later reference) can be obtained by tieing them at the center of each string. A form looking like a ring (call it ~\beta~) can be obtained from two strings ~[1, 3, 4]~ and ~[4, 6, 1]~ by connecting them at both ends. In this way various forms can be obtained. A part of such a form is called chain if it is a sequence of strings connected at their ends with the property that no two rings with the same integer appear on it. For example, ~\alpha~ contains chains ~[1, 3, 2], [1, 3, 4], [1, 3, 5], [2, 3, 1], [2, 3, 4]~, etc. of length 3, and ~\beta~ contains chains of length 4 such as ~[1, 3, 4, 6], [3, 4, 6, 1], [4, 6, 1, 3]~, where the length of a chain is the number of integers on it. Your task is to write a program to find the maximum length of possible chains.

Input

The first line of which contains an integer ~n~ ~(1 \le n \le 100)~, followed by ~n~ lines containing two integers separated by a single space character. The ~i + 1~-st line ~(1 \le i \le n)~ containing integers ~a~ and ~b~ ~(1 \le a < b \le 100)~ represents a string whose ends are rings with integers ~a~ and ~b~.

Output

The output file should contain the maximum length.

Sample Input 1

7
1 3
3 4
1 4
2 7
5 7
6 7
1 7

Sample Output 1

5

Sample Input 2

6
1 2
2 3
3 4
4 5
1 5
2 6

Sample Output 2

6

Sample Input 3

7
1 3
2 4
3 5
4 6 
6 7
2 6
4 7

Sample Output 3

4