NAUGHTY - Naughty and Balls

Mr. Naughty likes to play with balls. So his friend, Mr Nice, gave him n balls to play a game. Each ball has exactly two numbers (the number on the top and the number on the bottom). In one move Mr Naughty can rotate any ball so that its bottom now becomes the top. Mr Nice knows the minimum number of such moves that can make at least half of the balls show same number on their top. So to win Mr Nice's game, Mr Naughty should figure out the minimum number of moves. Its not always possible to make such moves that satisfy the given condition.In this case Mr Naughty should figure out that it is "Impossible" to make such moves.

Help Mr Naughty to win the game.

Input Format:

The first line contains a single integer n - the number of balls. The following n lines contain the description of all balls, one ball per line. Each description has a pair of non-negative integers not exceeding 10^5 - numbers on top and bottom. The first number in a line is the number on top, the second one - on the bottom. The number on the top of the ball may be same as the number on the bottom.
The numbers in the lines are separated by single spaces.

Output Format:

On a single line print a single integer - the minimum number of moves to win the game. If it is impossible to make the set funny, print "Impossible" (quotes for clarity).


1 ≤ n ≤ 10^5

Sample Input:

3 100
100 3
5 4

Sample Output:



In this case Mr Naughty can rotate the first ball so that number on the top becomes 100. Since two of the three balls have same number on their top (100), you do not need to change anything else, so the answer is 1.

Sample Input:

5 9
5 9
3 2
1 4
5 7

Sample Output:


Sample Input:

1 2
3 4
5 6 

Sample Output:


Problem Setter: Prateek Sachdev

hide comments
Shashank Tiwari: 2015-07-12 15:29:17

Just brute force .. check for each number

evilscientist: 2014-12-17 17:14:38

Got sigsiev for 10^5, accepted for 10^6.

Avinash: 2014-04-08 07:31:13

Hi Lalit, I don't think your test cases are correct . Not the ones which you have posted, but the ones against which program checks after submission.

Last edit: 2014-04-09 08:45:22
Sameer: 2014-02-08 09:12:31

Please check my submission I am getting WA again and again ID 11014665

Last edit: 2014-02-06 13:17:56
ABHISHEK004: 2014-02-08 09:12:31

very weak test cases...
accepted at both test cases of my own, one giving correct answer and one giving wrong answer....
please rejudge the problems..

Added by:darkshadows
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64