P10247 Pairing Pairs

This problem uses the original contest testdata. If you want to test an $O(n)$ solution, you can refer to the [enhanced version](https://www.luogu.com.cn/problem/P10248).

You are given $m$ pairs $(u_i, v_i)$ (guaranteed that $1 \le u_i < v_i \le n$, and all $m$ pairs are pairwise distinct). For each $i$, find an index $j$ such that the four numbers $u_i, v_i, u_j, v_j$ are all distinct from each other, or report that such a $j$ does not exist.

The first line contains two positive integers $n, m$, indicating the range of numbers in the pairs and the number of pairs. The next $m$ lines each contain two positive integers $u_i, v_i$, representing the $i$-th pair.

Output one line with $m$ non-negative integers. The $i$-th integer is the $j$ you found for this $i$. If no such $j$ exists, output $0$. If there are multiple valid $j$, output any one of them.

[Sample Explanation] The answer is not unique. For example, when $i = 4$: - $j$ can also be $3$, because the four numbers $2, 5, 1, 3$ are all distinct. So outputting `5 0 4 3 1` can also pass. - However, $j$ cannot be $1$, because among $2, 5, 1, 2$ there are repeated numbers. [Constraints] **This problem uses bundled judging.** Specifically, you can get the score of a subtask only if you pass all test points in that subtask. |Subtask ID|$n \le$|$m \le$|Special property|Score| |:-:|:-:|:-:|:-:|:-:| |$1$|$10^3$|$3\times 10^3$||$19$| |$2$|$=10^3$|$=3\times 10^5$||$16$| |$3$|$3\times 10^5$|$=n-1$|$u_i=i,v_i=i+1$|$3$| |$4$|$3\times 10^5$|$=n-1$|$v_i=i+1$|$22$| |$5$|$3\times 10^5$|$3\times 10^5$|Random testdata|$11$| |$6$|$3\times 10^5$|$3\times 10^5$||$29$| The specific generation process for subtask $5$: first I **specify** a set of $n, m$, then repeat the following process $m$ times: - Draw $x$ from $1 \sim n$, then draw $y$ from $1 \sim n-1$. - If $y \ge x$, then increase $y$ by $1$; otherwise swap $x, y$. - Check whether the pair $(x, y)$ has appeared before. If yes, go back to the first step. - Output $(x, y)$. For all data, it is guaranteed that $1 \le u_i < v_i \le n \le 3\times 10^5$, and $1 \le m \le 3\times 10^5$. Translated by ChatGPT 5