Problem D
Paintball
Marek and his schoolmates have just finished their studies at the university. They wanted to celebrate it with a game of paintball. After an hour of playing a very strange thing happened – everyone had exactly one bullet left. Marek, being a very curious person, wanted to know whether it’s possible that everyone will be hit exactly once provided nobody moves.
Task
You are given a description of the situation during a paintball game when every player has only one bullet. The description of the game consists of pairs of players who can see each other. If a player can see another player, he can fire at him. Your task is to find a target for each player such that everyone will be hit.
Input
The first line of input contains two space separated
integers
Output
If there is no assignment of targets such that everyone will
be hit, output Impossible. Otherwise output
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 2 2 3 1 3 |
2 3 1 |
Sample Input 2 | Sample Output 2 |
---|---|
3 2 1 2 1 3 |
Impossible |