Background

This problem uses the original contest testdata. If you want to test an $O(n)$ solution, you can refer to the enhanced version.

Problem Description

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.

Input Format

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 Format

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.

6 5
1 2
2 3
1 3
2 5
3 6

5 0 4 5 1

Hint

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

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