题目背景

本题为赛时原始数据。如果想要测试 $O(n)$，可以参考加强版。

题目描述

你有 $m$ 个数对 $(u_i,v_i)$（保证 $1\le u_i<v_i\le n$ 且 $m$ 个数对两两不同），对于每个 $i$ 找一个 $j$ 使得 $u_i,v_i,u_j,v_j$ 四个数两两不同，或报告不存在。

输入格式

输入的第一行有两个正整数 $n,m$ 表示数对中数字的范围和数对的个数。

之后 $m$ 行，其中的第 $i$ 行有两个正整数 $u_i,v_i$ 表示第 $i$ 个数对。

输出格式

输出一行 $m$ 个自然数，其中第 $i$ 个数表示你对这个 $i$ 找到的 $j$。若对应的 $j$ 不存在则输出 $0$。

若符合题意的 $j$ 有多个，任意输出一个都可以通过本题。

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

5 0 4 5 1

提示

【样例解释】

答案不唯一，例如 $i=4$ 时：

• $j$ 也可以是 $3$，因为 $2,5,1,3$ 四个数互不相同。所以输出 5 0 4 3 1 也可通过测试点。
• 然而 $j$ 不可以是 $1$，因为 $2,5,1,2$ 中存在相同数字。

【数据范围】

本题采用捆绑测试。 具体地，你只有通过一个子任务内所有测试点，才能拿到该子任务的分数。

子任务 $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$。