Background

A graph theory problem for Ysuperman’s template testing.

【Data deleted】.

Problem Description

Today’s template test is breadth-first traversal on an undirected graph. 【Data deleted】 quickly wrote the following code:

#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;
}

As you can see, this code reads an undirected graph with $n$ nodes and $m$ edges, then finds a “breadth-first traversal tree” rooted at $1$, and finally outputs the parent node index for every node.

However, note that the exact shape of this “breadth-first traversal tree” depends on the “input order of edges”. In other words, different input orders may lead to different parent arrays.

Now 【Data deleted】 tells you $n, m$, these $m$ edges, and the output of his code under some “edge input order”. You need to recover such an “edge input order”. If there are multiple edge input orders that match the output, you only need to output any one of them.

In particular, it is guaranteed that a solution exists, the undirected graph is connected, there are no self-loops (but there may be multiple edges).

Input Format

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 Format

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.

4 4
2 1
1 3
2 4
4 3
0 1 1 3

1 3
3 4
1 2
2 4

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

6 2
7 3
4 5
1 6
7 8
1 4
1 7
2 4
5 7

Hint

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