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.
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.
The first line of input contains two space separated
integers $N$ and
$2\leq N\leq 1\, 000$ and
$0\leq M\leq 5\, 000$,
where $N$ is the number of
players. Players are numbered $1,
2, \ldots , N$. $M$
lines follow, each line containing two space separated integers
$A$ and $B$ ($1\leq A < B\leq N$), denoting that
players $A$ and
$B$ can see each other.
Each pair of players appears at most once in the input.
If there is no assignment of targets such that everyone will
be hit, output Impossible. Otherwise output
$N$ lines. The
$i$-th line should contain
the number of the target of the $i$-th player. If there is more than
one solution, output any one.
|Sample Input 1
||Sample Output 1
|Sample Input 2
||Sample Output 2