Problem E
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 $N$ and $M$, satisfying $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.

Output

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.

3 3
1 2
2 3
1 3

2
3
1

3 2
1 2
1 3

Impossible