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