| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Собравшись в очередной раз, чтобы поиграть в домино, Люди Икс осознали, что игра им порядком надоела. Они решили придумать что-нибудь новое. Как обычно, с гениальной идеей выступил Гамбит. Он предложил следующую незамысловатую игру: по данному набору доминошек надо уметь определять длину самой длинной цепочки.
Каждая доминошка представляет собой пару чисел $a,ドル $b$ --- количество точек на двух половинах доминошки. Цепочкой называется последовательность доминошек, которую можно выложить в линию так, что для любых двух соседних доминошек с номерами $i,ドル $i+1$ в этой линии верно следующее: $b_i=a_{i+1}$. Доминошки нельзя поворачивать и переворачивать.
Люди Икс пока не научились оптимально играть в эту игру, поэтому обратились к вам за помощью.
В первой строке входного файла дано число $n$ (1ドル \le n \le 100000$) --- количество доминошек. В следующих $n$ строках даны пары чисел $a_i, b_i$ (0ドル \le b_i \le a_i \le 10^9$) --- описание доминошек.
В единственной строке выходного файла выведите одно число --- максимальную длину цепочки из доминошек.
7 2 6 5 6 2 5 2 2 6 8 2 2 0 2
6