Background

Welcome to Lord Selim’s pleasure banquet!

Problem Description

There are $n$ guests at the banquet, numbered from $1$ to $n$. To better control the power of the Shadow, Selim requires that exactly $n-1$ guests are each dominated by exactly one other guest, and the remaining one becomes the overall dominator, dominating the other $n-1$ guests. The direct domination relationships among the guests form a rooted tree.

For this tree, if the parent of node $a$ is $b$, then $b$ dominates $a$, and $b$ is called the direct dominator of $a$. Also, domination is transitive: if $a$ dominates $b$ and $b$ dominates $c$, then $a$ also dominates $c$.

There are also $m$ domination conditions. A domination condition is an ordered pair $(x,y)$ ($1 \le x,y \le n$, $x \neq y$). If guest $x$ dominates $y$, then the power of the Shadow increases by $1$. If $y$ dominates $x$, then the power of the Shadow decreases by $1$. If neither dominates the other, then the power of the Shadow does not change. The initial power of the Shadow is $0$.

As Selim’s considerate servant, Songque needs to organize a banquet, so she must arrange the domination relationships for everyone. Selim does not care how large the power of the Shadow can become; she only needs the power of the Shadow to stay non-negative. Can you help her construct the final domination relationships?

If there are multiple solutions, you only need to output any one. It is guaranteed that for any valid input, a solution exists.

Input Format

The first line contains two positive integers $n,m$ ($1 \le n \le 1\times 10^5,\ 1 \le m \le 2\times 10^5$), separated by spaces, representing the number of guests and the number of domination conditions.

The next $m$ lines each contain two positive integers $x,y$ ($1 \le x,y \le n,\ x\neq y$), separated by a space, representing a domination condition $(x,y)$. Domination conditions may be repeated, and opposite conditions may also appear, meaning both $(x,y)$ and $(y,x)$ can appear. Each domination condition does not affect the others.

Output Format

Output one line with $n$ numbers. The $i$-th number represents the index of the direct dominator of guest $i$. The overall dominator’s direct dominator index is $0$.

5 5
3 1
2 3
1 3
2 4
3 5

2 3 0 3 3 

Hint

In the sample, the final power of the Shadow is $1-1-1+0+1=0$, which satisfies the non-negative requirement.

Translated by ChatGPT 5