Restoring Edge Input Order for BFS Tree on an Undirected Graph

You are given an undirected graph with \(n\) vertices and \(m\) edges. The graph has no self-loop (but may have multiple edges) and is guaranteed to be connected. In addition, you are given an array \(P[1\ldots n]\) representing the output of a breadth-first search (BFS) starting from vertex \(1\) that was performed on the graph. In this BFS tree, \(P[1]=0\) and for every \(v\) with \(2 \le v \le n\) it holds that \(P[v]\) is the parent of \(v\) in the BFS tree.

The twist is that the BFS tree produced by the following C++ algorithm:

// (C++ code snippet similar to the given one)

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

depends on the order in which the edges were provided in the input. That is, the edge input order can change the structure of the BFS tree (and hence the parent array \(P\)).

Your task is: given \(n\), \(m\), the list of \(m\) edges, and a resulting parent array \(P\) (which is known to come from some valid edge input order), restore one possible edge input order that produces exactly the given BFS parent array when the above BFS algorithm is run.

Note:

• It is guaranteed that there exists at least one solution.
• If more than one valid edge input order exists, output any one of them.
• The graph can have multiple edges between the same pair of vertices.

inputFormat

The input consists of:

1. The first line contains two integers \(n\) and \(m\) \( (1 \le n \le 10^5,\, 1 \le m \le 10^5)\), representing the number of vertices and edges respectively.
2. The next \(m\) lines each contain two integers \(u\) and \(v\) \((1 \le u, v \le n,\, u \ne v)\), representing an undirected edge between \(u\) and \(v\).
3. The last line contains \(n\) integers, where the \(i\)th integer represents \(P[i]\). It is guaranteed that \(P[1] = 0\), and for every \(2 \le i \le n\), there is at least one occurrence of an edge between \(P[i]\) and \(i\) in the edge list.

outputFormat

Output exactly \(m\) lines, each line containing two integers \(u\) and \(v\). These lines represent one possible permutation of the \(m\) edges such that, when the edges are added to the graph in that order (thereby determining the order of neighbors in each adjacency list), running the BFS algorithm starting from vertex \(1\) would produce the given parent array \(P[1\ldots n]\).

sample

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

1 2
1 3
3 4
2 3