Лимит времени 3000/5000/5000/5000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ilir Capuni.
Kruja Boys
Kruja has a specific architecture as all
the houses are on the same street. Boys live in
some odd numbered houses (the left side of the
street), while girls live on the even side
houses. N boys fell in love (each of them
with a different girl), but they are too
shy and they do not want to meet with their
friends when they are going on a date, so
they can avoid being teased by their friends.
Question:
You want to develop a match-making website
hence, each boy has inserted his own address
and the address of his valentine. Find the
maximal number of couples for which paths of
the boys while going to their girlfriends do
not intersect.
Input specification
You will be given an integer number (n) at the beginning
where 1 ≤ n ≤ 10000. Then in the following n lines,
you will be given two integers,
home number of boy and matching girl where home numbers are
less than 50000.
Output specification
Show just one number: maximal number of couples
for which paths do not intersect.
Sample Input
7
13 2
1 4
5 10
3 8
9 12
7 6
11 14
|
Sample Output
5
|
Explanation: following 5 boys can meet
with the girls at the same time without any intersection.
1
3
5
9
11
Для отправки решений необходимо выполнить вход.
|