One-way streets#5490
Soudislavl is plagued by severe traffic congestion, and the situation has been deteriorating each year. In response, the city authorities have decided to convert all streets to one-way to alleviate the problem. However, without proper planning, there is a risk that some parts of the city may become inaccessible from others. To address this, the Ministry of Transport has compiled a list of pairs of city intersections that must remain connected after the conversion.
Your task is to write a program that assigns directions to all the city's streets so that all connectivity requirements are met.
The first line contains three integers , , and (1 \le n \le 50000, 0 \le m, k \le 200000), representing the number of city intersections, streets, and connectivity requirements, respectively. Intersections are numbered from to . The next lines each contain a pair of numbers a_i, b_i (1 \le a_i, b_i \le n, a_i \ne b_i), describing a street. Initially, all streets are bidirectional. There is no more than one street between any pair of intersections. The following lines describe the connectivity requirements. Each line contains a pair of integers p_i, q_i (1 \le p_i, q_i \le n, p_i \ne q_i), indicating that after the streets are converted to one-way, there must be a path from p_i to q_i.
On the first line, output YES or NO, indicating whether it is possible to assign a one-way direction to all streets to satisfy all requirements. If it is possible, output additional lines, each containing a pair c_i, d_i, specifying the direction of traffic on the -th street from the input. This means traffic should flow from intersection c_i to intersection d_i. Ensure that the order of the streets matches the input data. If multiple solutions exist, you may output any one of them.
Example 1