Background

Day 2 Problem C.

This statement is translated from EGOI2023 sopsug.

Problem Description

Gravel Heap is an undeveloped residential area on the outskirts of Lund. Currently, all necessary infrastructure is being built, including the most important one: waste disposal. As in many parts of Sweden, an automatic vacuum collection system will be used to collect waste. The idea is to use air pressure to transport waste through underground pipes.

In Gravel Heap, there are $N$ buildings, numbered from $0$ to $N-1$. Your task is to connect some pairs of buildings with pipes. If you connect a pipe from building $u$ to $v$, then $u$ will send all its waste to $v$ (but not the other way around). Your goal is to build a network of $N-1$ pipes so that all waste eventually ends up in a single building. In other words, you want the whole network to be a rooted tree with all edges pointing towards the root.

However, there are already $M$ pipes built between buildings. These pipes must be included in your network. These pipes are directed and can only transport waste in one direction.

In addition, there are $K$ ordered pairs of buildings between which it is impossible to build a pipe. These pairs are ordered, so if it is impossible to build a pipe from $u$ to $v$, it may still be possible to build a pipe from $v$ to $u$.

Input Format

The first line contains three integers $N, M, K$.

The next $M$ lines each contain two distinct integers $a_i, b_i$, meaning there is already a pipe from $a_i$ to $b_i$.

The next $K$ lines each contain two distinct integers $c_i, d_i$, meaning it is impossible to build a pipe from $c_i$ to $d_i$.

All $M+K$ ordered pairs are pairwise distinct. Note that $(u, v)$ and $(v, u)$ are considered two different pairs.

Output Format

If there is no solution, output NO.

Otherwise, output $N-1$ lines, each containing two integers $u_i, v_i$, meaning there is a pipe from $u_i$ to $v_i$. You may output the pipes in any order. If there are multiple solutions, you may output any of them. Remember that all $M$ existing pipes must be included in the answer.

5 1 8
4 1
3 1
3 4
3 2
0 2
0 4
2 4
1 0
2 0

4 1
3 0
1 3
2 3

5 4 0
1 0
2 3
3 4
4 2

NO

3 0 1
0 1

1 0
2 0

4 0 2
0 1
1 0

2 0
3 0
1 3

Hint

Explanation for Samples $1$ and $2$.

The figure below shows the first two samples. Blue edges indicate existing pipes, and red dashed edges indicate pipes that cannot be built.

The left figure shows Sample $1$ and the solution given by the sample output. Black edges indicate newly built pipes. In this network, all waste will be collected in building $0$. This is not the only solution; for example, the pipe from $1$ to $3$ can be replaced by the pipe from $0$ to $1$, and the result is still a valid solution.

For Sample $2$, from the right figure we can see that due to the cycle $(2, 3, 4)$, the problem has no solution.

Constraints

For all testdata, $2 \le N \le 3 \times 10^5$, $0 \le M \le 3 \times 10^5$, $0 \le K \le 3 \times 10^5$, $0 \le a_i, b_i \le N-1$, $0 \le c_i, d_i \le N-1$.

• Subtask 1 ($12$ points): $M = 0$, $K = 1$.
• Subtask 2 ($10$ points): $M = 0$, $K = 2$.
• Subtask 3 ($19$ points): $K = 0$.
• Subtask 4 ($13$ points): $N \le 100$.
• Subtask 5 ($17$ points): It is guaranteed that there exists a solution with $0$ as the root.
• Subtask 6 ($11$ points): $M = 0$.
• Subtask 7 ($18$ points): No additional constraints.

Translated by ChatGPT 5