Игра в домино

시간 제한2초메모리 제한1024 MB

요약

각 도미노의 b가 다음 도미노의 a와 같아야 한다는 조건 아래, 뒤집지 않고 나열할 수 있는 가장 긴 도미노 사슬의 길이를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 동적 계획법, 정렬, 해시맵
정답자: 아직 제출이 없습니다

문제

Собравшись в очередной раз, чтобы поиграть в домино, Люди Икс осознали, что игра им порядком надоела. Они решили придумать что-нибудь новое. Как обычно, с гениальной идеей выступил Гамбит. Он предложил следующую незамысловатую игру: по данному набору доминошек надо уметь определять длину самой длинной цепочки.

Каждая доминошка представляет собой пару чисел $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$ ) --- описание доминошек.

출력

В единственной строке выходного файла выведите одно число --- максимальную длину цепочки из доминошек.

예제1

예제 1
입력
```
7
2 6
5 6
2 5
2 2
6 8
2 2
0 2
```
예상 출력
```
6
```