Hide

# Problem APaintball

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.

## 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.

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

Hide