31449번 - Close scores 스페셜 저지다국어

문제

The Olympic football tournament has started and, of course, France is going to win by a landslide, thus killing all the suspense. Or is it? Until now, only ties happened: not very exciting...

To hype the event, you would like every remaining match not to be a tie, and among all such configurations, you would like to find one which minimises the difference between the best score and the worst score. Remember that the score of a team is the number of its won matches minus its lost matches.

Given the list of remaining matches, find such an optimal configuration of matches.

입력

The first line contains two space-separated integers $N$ and $M$; $N$ is the number of teams, and $M$ is the number of remaining matches. This line is followed by $M$ lines: the $k$^th such line contains two space-separated integers $x_k$ and $y_k,ドル indicating that the $x_k$^th team has yet to play against the $y_k$^th team during the $k$^th match.

출력

The output should contain $M$ lines. The $k$^th such line should contain a single integer: the index of the team winning the $k$^th match (which should be equal to either $x_k$ or $y_k$).

제한

• 2ドル \le N \le 100,円 000$
• 1ドル \le M \le 100,円 000$
• 1ドル \le x_k < y_k ⩽ N$ for all $k \le M$

힌트