Dominoes
Problem
A chain of N dominoes has been laid out on the table. A knuckle is understood as a pair of any non-negative numbers, each does not exceed 100. There are no two identical knuckles in the set (as in dominoes). It is impossible to rearrange the knuckles, but you can rotate any knuckle, getting a knuckle 2-1 from a knuckle 1-2.
Find the longest chain of dominoes you can get. A chain should be understood as a sequence of knuckles, in which the second number of the first knuckle is equal to the first number of the second.
Input
the first line specifies the number
N – the number of tiles laid out (
\(0<N<10000\)). This is followed by
N pairs of numbers, two per line.
Imprint
The program should output a single number – maximum chain length.
Examples
| # |
Input |
Output |
| 1 |
5
1 2
23
5 4
5 5
5 1 |
3 |
Explanation: if you flip the third tile, a chain is formed: 4-5 5-5 5-1.