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