P9534 [YsOI2023] Breadth-First Traversal

A graph theory problem for Ysuperman’s template testing. 【Data deleted】.

Today’s template test is breadth-first traversal on an undirected graph. 【Data deleted】 quickly wrote the following code: ```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

The first line contains two positive integers $n, m$, representing the number of nodes and edges in the undirected graph. The next $m$ lines each contain two integers $u, v$, indicating that there is an undirected edge between $u$ and $v$. The last line contains $n$ integers, which are the output of 【Data deleted】’s code. (From the statement, this is the parent node index for nodes $1 \sim n$ in the “breadth-first traversal tree” obtained under some “edge input order”.)

Output $m$ lines. Each line contains two integers $u, v$ indicating an undirected edge between $u$ and $v$. Your output order represents the “edge input order” you provide. Please note that if the input graph contains $k$ edges between $u$ and $v$, then your output must also contain exactly $k$ edges between $u$ and $v$. If multiple “edge input orders” are valid, **any one of them will be judged correct**. Also, since the edges are undirected, the **order of the two endpoints of an edge does not affect judging**.

#### Explanation of Sample 1 Just run 【Data deleted】’s code directly. If you do not change the edge input order and feed the following data into 【Data deleted】’s code: ``` 4 4 2 1 1 3 2 4 4 3 ``` Then his code produces: ``` 0 1 1 2 ``` If you output in the order given by Sample 1, i.e., feed the following data into his code: ``` 4 4 1 3 3 4 1 2 2 4 ``` Then the output is: ``` 0 1 1 3 ``` #### Constraints For the first $10\%$ of the data, $n\le 8$, $m\le 10$. For the first $40\%$ of the data, $n\le 1000$, $m\le 2000$. Another $10\%$ of the data satisfies $m=n-1$. For $100\%$ of the data, $1\le n\le 10^5$, $1\le m\le 2\times 10^5$. #### Hint Why can there be multiple edges? Because they were too lazy to deduplicate them, and this person is too lazy to check for multiple edges when making graph problems. The checker for this problem is provided as an attachment. Translated by ChatGPT 5