Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VPDOMINO - VPDOMINO

Cho N quân domino, quân thứ i (1 ≤ i ≤ N) ghi hai số nguyên A­i, Bi  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 ≤ N ≤ 105)

Dòng 2…N+1: dòng i + 1 ghi hai số nguyên Ai, Bi (0 ≤ Ai≤Bi ≤ 109

Output

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

Example

Input:

7

2 6

5 6

2 5

2 2

6 8

2 2

0 2 

Output: 6

Được gửi lên bởi:Thương
Ngày:2014-11-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc năm 2014-2015

hide comments
2017-06-19 20:28:13
easyhoon
2016-05-04 18:10:18
nhu lol
2015-07-26 11:41:46 Phạm Ngọc Hiếu
e bị sai test mn ơi :'( chả bt sai gì
2014-12-02 11:07:50 [$Zeus$]
Để Quicksort Random thì TLE, để lại là Div 2 thì lại đc :v :v đúng là do ăn ở
2014-11-15 15:23:51 Thanga2pbc
ai giải thích em test vd với??
2014-11-15 15:15:12 livw
QHĐ chuẩn
2014-11-13 15:43:36 Ngoc Jr7
Ai cho xin test 5 với. cứ bị wa test 5 mà chả hiểu sao sai gì.
2014-11-12 11:57:27 Thcs Ðặng Chánh Kỷ
Ac phát đầu, chả hiểu sao các bạn sub lại ko ac
2014-11-08 11:37:56 2ez
test gì hiểm nhỉ? mình sub 1 phát- chương trình chính 10 dòng?
Bài mình còn sai test đơn giản nữa mà vẫn AC
PS: anh có thể cho biết nó là test nào không =))))))))))

2
2 2
2 2

output: 3
answer: 2

Last edit: 2014-11-10 17:24:08
2014-11-04 15:23:41 Bitagi97
test là test gì mà sao nhiều người wa vậy :??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.