Taco Domino Sequence

Julia has a collection of domino pieces where each domino is represented as a tuple of two integers between 0 and 6. She wants to form the longest sequence such that for every two consecutive dominoes in the sequence, the number on the touching sides is the same.

Formally, if you have a domino represented as \((a, b)\) followed by a domino \((c, d)\), then the sequence is valid only if \(b = c\). A domino can be flipped; that is, a domino \((a, b)\) can also be used as \((b, a)\).

Your task is to, given \(n\) domino pieces, determine the maximum number of domino pieces that can be arranged into a valid sequence.

Note: Each domino can be used at most once in the sequence.

For example, for input dominoes [(1,2), (2,3), (3,4)], a valid sequence is (1,2) -> (2,3) -> (3,4) and the answer is 3.

inputFormat

The first line contains an integer (n) representing the number of domino pieces.\nEach of the next (n) lines contains two integers, representing the two numbers on a domino piece.

outputFormat

Output a single integer, which is the maximum number of domino pieces that can form a valid sequence.## sample

3
1 2
2 3
3 4

3