VPDOMINO

View as PDF

Submit solution

Points: 0.58 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc nãm 2014-2015
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~N~ quân domino, quân thứ ~i~ ~(1 \leq i \leq N)~ ghi hai số nguyên ~A_{­i}~, ~B_{i}~ trên tương ứng hai nửa trái, phải. Cần xếp các quân domino thành một dãy thẳng theo quy tắc:

  • Không xoay hay lật các quân domino
  • Hai quân domino xếp kề nhau phải có số ở nửa phải quân bên trái trùng với số ở nửa trái quân bên phải.

Hãy xác định dãy domino dài nhất xếp được có bao nhiêu quân.

Input

  • Dòng ~1~: số nguyên ~N~ ~(1 \leq N \leq 10^{5})~
  • Dòng ~2~ ...~N + 1~: dòng ~i + 1~ ghi hai số nguyên ~A_{i}~, ~B_{i}~ ~(0 \leq A_{i} \leq B_{i} \leq 10^{9})~

Output

Số nguyên là số quân domino nhiều nhất xếp được thành một dãy.

Sample Input

7
2 6
5 6
2 5
2 2
6 8
2 2
0 2

Sample Output

6

Comments

Please read the guidelines before commenting.


There are no comments at the moment.