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