Problem Background

Day 2 Problem C.

The problem statement is translated from EGOI2023 sopsug.

Problem Description

Sopsug is an unfinished residential area on the outskirts of Lund. Currently, all necessary infrastructure is under construction, including the most important one: waste disposal. Like many regions in Sweden, an automatic vacuum collection system will be used to collect waste. The principle is to use air pressure to transport waste through pipes underground.

There are $N$ buildings in Sopsug, numbered from $0$ to $N-1$. Your task is to connect several pairs of buildings with pipes. If you connect a pipe between buildings $u$ and $v$, $u$ will transport all its waste to $v$ (but not vice versa). Your goal is to establish a network consisting of $N-1$ pipes such that all waste eventually ends up in one building. In other words, you want the entire network to form a rooted tree with all edges pointing towards the root.

However, $M$ pipes have already been constructed between buildings. These pipes must be included in your network. These pipes are directional and can only transport waste in one direction.

Additionally, there are $K$ pairs of buildings where no pipe can be constructed. These pairs of buildings are ordered, so if it is impossible to construct a pipe from $u$ to $v$, it may still be possible to construct 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$, indicating that there is already a pipe from $a_i$ to $b_i$.

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

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

Output Format

If there is no solution, output NO.

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

4 1
3 0
1 3
2 3

Sample Input #2

5 4 0
1 0
2 3
3 4
4 2

Sample Output #2

NO

Sample Input #3

3 0 1
0 1

Sample Output #3

1 0
2 0

Sample Input #4

4 0 2
0 1
1 0

Sample Output #4

2 0
3 0
1 3

Notes

Sample Explanation for Samples 1 and 2

The following diagram illustrates the first two samples. Blue edges represent already existing pipes, and red dashed edges represent pipes that cannot be built.

The left diagram shows Sample 1 and the sample output solution, with black edges representing 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$ could be replaced by a pipe from $0$ to $1$, and it would still be a valid solution.

For Sample 2, as shown in the right diagram, the problem has no solution due to the presence of the cycle $(2, 3, 4)$.

Data Range

For all data, $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): A solution exists with $0$ as the root.
• Subtask 6 (11 points): $M = 0$.
• Subtask 7 (18 points): No additional constraints.

见题面 Input 部分

见题面 Output 部分