P9534 [YsOI2023] 广度优先遍历
题目背景
Ysuperman 模板测试的图论题。
【数据删除】
题目描述
今天的模板测试是无向图上的广度优先遍历，【数据删除】马上写好了代码：
```cpp
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100005;
vector G[maxn];
queue q;
int pa[maxn];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i > 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,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 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。