Dizzy Cows

The cows have started racing each other around the farm, but running in circles makes them dizzy, and a dizzy cow gives no milk. Farmer John wants to turn every two-way path into a one-way path so that the farm no longer contains any cycle that would let a cow loop back to where she started. A cycle is a sequence of one or more paths that begins and ends at the same pasture.

The farm has $N$ pastures ($1 \le N \le 10^5$) numbered $1$ through $N$. They are joined by $M_1$ one-way paths ($1 \le M_1 \le 10^5$) and $M_2$ two-way paths ($1 \le M_2 \le 10^5$). No path joins a pasture to itself, but two different pastures may be joined by several paths, and not every pair of pastures is necessarily reachable from one another.

Each one-way path goes from pasture $A_i$ to pasture $B_i$ ($1 \le A_i, B_i \le N$). Each two-way path joins pastures $X_i$ and $Y_i$ ($1 \le X_i, Y_i \le N$). The one-way paths are guaranteed to contain no cycle, and they must be kept exactly as they are. Your task is to choose a direction for every two-way path so that the whole farm — now built from one-way paths only — contains no cycle.

For example, suppose two-way paths join pastures $1$ and $3$, $2$ and $3$, and $2$ and $4$, while one-way paths run from $1$ to $2$ and from $4$ to $3$:

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

Orienting the two-way paths as $1 \to 3$, $2 \to 3$, and $2 \to 4$ leaves the farm free of cycles:

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

• Line $1$: three space-separated integers $N$, $M_1$, and $M_2$.
• Lines $2 \ldots 1 + M_1$: each line contains two space-separated integers $A_i$ and $B_i$, describing a one-way path from $A_i$ to $B_i$.
• Lines $2 + M_1 \ldots 1 + M_1 + M_2$: each line contains two space-separated integers $X_i$ and $Y_i$, describing a two-way path joining $X_i$ and $Y_i$.

Assign directions to the two-way paths with the following canonical rule, which makes the answer unique:

1. Consider only the one-way paths. Repeatedly take the smallest-numbered pasture that currently has no incoming one-way path, append it to an ordering, and then remove that pasture together with its outgoing one-way paths. This produces the lexicographically smallest topological ordering of the one-way subgraph.
2. Direct each two-way path from whichever of its two endpoints comes earlier in that ordering to the endpoint that comes later.

Print $M_2$ lines. Line $i$ contains two space-separated integers: the tail pasture followed by the head pasture of the $i$-th two-way path after it has been oriented. The two-way paths must appear in the same order as in the input.

If the one-way paths themselves contain a cycle, so that no valid orientation exists, print -1 on a single line instead.