P10521 [XJTUPC 2024] Selim’s Banquet.

Welcome to Lord Selim’s pleasure banquet! 

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.

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

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