Domino#10004
Togrul has invented a simple game for you and wants to see how well you can handle it.
The game is as follows: given a set of dominoes, determine the length of the longest possible chain.
Each domino is represented by a pair of numbers and — the number of dots on the two halves of the domino.
A chain is defined as a sequence of dominoes that can be arranged in a line such that for any two consecutive dominoes with indices and i + 1, the following condition holds: b[i] = a[i+1].
To find the correct answer, Togrul asks you to write a program that solves this problem.
The first line contains a single integer n~(1 \le n \le 10^5) — the number of dominoes.
The following lines contain pairs of integers a_i, b_i~(0 \le a_i \le b_i \le 10^9) — the description of the dominoes.
Print one integer — the maximum length of a chain of dominoes.
Beispiel 1