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 nonnegative 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).
Constraints:
1 ≤ n ≤ 10^5
Sample Input:
3
3 100
100 3
5 4
Sample Output:
1
Explanation:
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
5 9
5 9
3 2
1 4
5 7
Sample Output:
0
Sample Input:
3
1 2
3 4
5 6
Sample Output:
Impossible
Problem Setter: Prateek Sachdev
hide comments
Shashank Tiwari:
20150712 15:29:17
Just brute force .. check for each number 

evilscientist:
20141217 17:14:38
Got sigsiev for 10^5, accepted for 10^6. 

Avinash:
20140408 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: 20140409 08:45:22 

Sameer:
20140208 09:12:31
Please check my submission I am getting WA again and again ID 11014665 Last edit: 20140206 13:17:56 

ABHISHEK004:
20140208 09:12:31
very weak test cases...

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