Pairing Pairs

你有 $m$ 个数对 $(u_i,v_i)$（保证 $1\le u_i<v_i\le n$ 且 $m$ 个数对两两不同），对于每个 $i$ 找一个 $j$ 使得 $u_i,v_i,u_j,v_j$ 四个数两两不同，或报告不存在。 ## Input 输入的第一行有两个正整数 $n,m$ 表示数对中数字的范围和数对的个数。 之后 $m$ 行，其中的第 $i$ 行有两个正整数 $u_i,v_i$ 表示第 $i$ 个数对。 ## Output 输出一行 $m$ 个自然数，其中第 $i$ 个数表示你对这个 $i$ 找到的 $j$。若对应的 $j$ 不存在则输出 $0$。 若符合题意的 $j$ 有多个，任意输出一个都可以通过本题。 [samples] ## Background 本题为赛时原始数据。如果想要测试 $O(n)$，可以参考[加强版](https://www.luogu.com.cn/problem/P10248)。 ## Note 【样例解释】 答案不唯一，例如 $i=4$ 时： - $j$ 也可以是 $3$，因为 $2,5,1,3$ 四个数互不相同。所以输出 `5 0 4 3 1` 也可通过测试点。 - 然而 $j$ 不可以是 $1$，因为 $2,5,1,2$ 中存在相同数字。 【数据范围】 **本题采用捆绑测试。** 具体地，你只有通过一个子任务内所有测试点，才能拿到该子任务的分数。 |子任务编号|$n\le$|$m\le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |$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$|数据随机|$11$| |$6$|$3\times 10^5$|$3\times 10^5$||$29$| 子任务 $5$ 的具体生成过程：首先我**指定**一组 $n,m$，接下来执行 $m$ 次如下流程： - 在 $1\sim n$ 内抽取 $x$，然后在 $1\sim n-1$ 内抽取 $y$。 - 若 $y\ge x$ 则把 $y$ 增加 $1$，否则交换 $x,y$。 - 判断数对 $(x,y)$ 是否出现过，若是，回到第一步。 - 输出 $(x,y)$。 对于全部数据，保证 $1\le u_i<v_i\le n\le 3\times 10^5$，$1\le m\le 3\times 10^5$。