Eliminating Cycles by Direction Assignment

The cows are racing around the farm via various cow paths, but when they run in cycles they become dizzy and produce less milk. Farmer John has decided to eliminate all cycles by converting every two‐way cow path into a one‐way cow path so that the overall network contains no cycles. A cycle is defined as a path (possibly using several cow paths) that starts and ends at the same pasture.

The farm consists of \(N\) pastures numbered from 1 to \(N\). There are \(M_1\) one‐way cow paths and \(M_2\) two‐way cow paths. Each one‐way cow path goes from pasture \(A_i\) to pasture \(B_i\) and is guaranteed to be acyclic. Each two‐way cow path connects pastures \(X_i\) and \(Y_i\). Your task is to assign a direction to each two‐way cow path so that when combined with the given one‐way cow paths, the entire network is acyclic.

Example:

1-->2
|  /|
| / |
|/  |
3<--4

Here, the two‐way paths are between pastures (1,3), (2,3), and (2,4) while the one‐way paths are 1\(\rightarrow\)2 and 4\(\rightarrow\)3. One valid solution is to direct the two‐way paths as follows: 1\(\rightarrow\)3, 2\(\rightarrow\)3, and 3\(\rightarrow\)4, giving:

1-->2
|  /|
| / |
v  v 
3<--4

Hint: A good strategy is to compute a topological order of the pastures using the one‐way paths, then for each two‐way path \((X_i, Y_i)\) assign the direction from the pasture that appears earlier in the order to the one appearing later.

inputFormat

The first line contains three integers: \(N\) (\(1 \leq N \leq 10^5\)), \(M_1\) (\(1 \leq M_1 \leq 10^5\)), and \(M_2\) (\(1 \leq M_2 \leq 10^5\)).

The next \(M_1\) lines each contain two integers \(A_i\) and \(B_i\), representing a one‐way cow path from pasture \(A_i\) to pasture \(B_i\).

The following \(M_2\) lines each contain two integers \(X_i\) and \(Y_i\), representing a two‐way cow path between pastures \(X_i\) and \(Y_i\).

outputFormat

Output \(M_2\) lines. For each two‐way cow path (in the order of input), output two integers representing the directed edge after conversion. The direction should be assigned such that the final graph (including all one‐way paths and your converted paths) has no cycles.

sample

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

1 3
2 3
3 4