{"raw_statement":[{"iden":"background","content":"Ysuperman 模板测试的图论题。\n\n【数据删除】"},{"iden":"statement","content":"今天的模板测试是无向图上的广度优先遍历，【数据删除】马上写好了代码：\n\n```cpp\n#include <cstdio>\n#include <cstring>\n#include <iostream>\n#include <algorithm>\n#include <vector>\n#include <queue>\nusing namespace std;\nconst int maxn = 100005;\nvector<int> G[maxn];\nqueue<int> q;\nint pa[maxn];\nint main()\n{\n    int n, m;\n    cin >> n >> m;\n    for (int i = 1; i <= m; ++i)\n    {\n        int u, v;\n        cin >> u >> v;\n        G[u].push_back(v);\n        G[v].push_back(u);\n    }\n    memset(pa, -1, sizeof pa);\n    q.push(1);\n    pa[1] = 0;\n    while (!q.empty())\n    {\n        int u = q.front();\n        q.pop();\n        for (auto v : G[u])\n        {\n            if (pa[v] != -1)\n                continue;\n            pa[v] = u;\n            q.push(v);\n        }\n    }\n    for (int i = 1; i <= n; ++i)\n    {\n        cout << pa[i];\n        if (i != n)\n            cout << \" \";\n    }\n    cout << endl;\n    return 0;\n}\n```\n\n如你所见，这份代码会输入一个 $n$ 个点 $m$ 条边的无向图，并且求出这张图以 $1$ 为根的一棵“广度优先遍历树”，最后输出所有点的父亲节点编号。\n\n不过值得注意的是，这棵“广度优先遍历树”的具体形态和“边的输入顺序”有关，也就是说，不同的输入顺序可能会得到不同的父亲节点编号。\n\n现在【数据删除】告诉了你 $n,m$、这 $m$ 条边以及在某个“边输入顺序”情况下他的代码的输出，你需要还原出这个“边输入顺序”。如果有多种边输入顺序对应的都是这样的输出，你**只需要输出其中任意一种**即可。\n\n特别的，保证有解，且无向图连通，无自环（但是有可能有重边）。"},{"iden":"input","content":"第一行两个正整数 $n,m$ 分别表示无向图的点数和边数。\n\n接下来 $m$ 行每行两个整数 $u,v$ 表示存在 $u$ 与 $v$ 之间存在一条无向边。\n\n最后一行 $n$ 个整数表示【数据删除】代码的输出。（由题意可知他输出的是某个“边输入顺序”情况下他得到的“广度优先遍历树”中 $1\\sim n$ 这些节点的父亲节点编号）"},{"iden":"output","content":"输出包含 $m$ 行，每行两个整数 $u,v$ 表示 $u$ 和 $v$ 之间存在一条无向边，你的输出顺序表示你给出的“边输入顺序”。\n\n请注意，你需要保证如果输入给出的图中 $u,v$ 间连了 $k$ 条边，那么你给出的图中 $u,v$ 间也要连有 $k$ 条边。\n\n如果有多种“边输入顺序”合法，**输出其中任意一种都会被判断为正确**。另外，由于是无向边，所以你输出的**一条边两个点的排列顺序对答案判定没有影响**。"},{"iden":"note","content":"#### 样例 1 解释\n\n直接运行【数据删除】的代码即可。\n\n如果不改变边输入顺序，将下面数据输入【数据删除】的代码：\n\n```\n4 4\n2 1\n1 3\n2 4\n4 3\n```\n\n他的代码跑出来结果如下：\n\n```\n0 1 1 2\n```\n\n如果按照样例 1 输出给出的顺序，即，将下面数据输入他的代码：\n\n```\n4 4\n1 3\n3 4\n1 2\n2 4\n```\n\n输出为：\n\n```\n0 1 1 3\n```\n\n#### 数据范围\n\n对于前 $10\\%$ 的数据，满足 $n\\le 8$，$m\\le 10$。\n\n对于前 $40\\%$ 的数据，满足 $n\\le 1000$，$m\\le 2000$。\n\n另有 $10\\%$ 的数据，满足 $m=n-1$。\n\n对于 $100\\%$ 的数据，满足 $1\\le n\\le 10^5$，$1\\le m\\le 2\\times 10^5$。\n\n#### 提示\n\n为什么有可能会有重边，因为懒得去重了，这个家伙出图论题就是懒得判重边的（）\n\n附件下发了本题 checker。"}],"translated_statement":null,"sample_group":[["4 4\n2 1\n1 3\n2 4\n4 3\n0 1 1 3","1 3\n3 4\n1 2\n2 4\n"],["8 9\n7 8\n6 1\n5 4\n7 1\n4 1\n3 7\n2 6\n7 5\n2 4\n0 6 7 1 4 1 1 7","6 2\n7 3\n4 5\n1 6\n7 8\n1 4\n1 7\n2 4\n5 7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}