You are working at a factory manufacturing many different products. Products have to be processed on a number of different machine tools. Machine shops with these machines are connected with conveyor lines to exchange unfinished products. Each unfinished product is transferred from a machine shop to another through one or more of these conveyors.
As the orders of the processes required are not the same for different types of products, the conveyor lines are currently operated in two-way. This may induce inefficiency as conveyors have to be completely emptied before switching their directions. Kaizen (efficiency improvements) may be found here!
Adding more conveyors is too costly. If all the required transfers are possible with currently installed conveyors operating in fixed directions, no additional costs are required. All the required transfers, from which machine shop to which, are listed at hand. You want to know whether all the required transfers can be enabled with all the conveyors operated in one-way, and if yes, directions of the conveyor lines enabling it.
The input consists of a single test case of the following format.
$n$ $m$ $x_1$ $y_1$ . . . $x_m$ $y_m$ $k$ $a_1$ $b_1$ . . . $a_k$ $b_k$
The first line contains two integers $n$ ($2 \leq n \leq 10 000$) and $m$ ($1 \leq m \leq 100 000$), the number of machine shops and the number of conveyors, respectively. Machine shops are numbered $1$ through $n$. Each of the following $m$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i < y_i \leq n$), meaning that the $i$-th conveyor connects machine shops $x_i$ and $y_i$. At most one conveyor is installed between any two machine shops. It is guaranteed that any two machine shops are connected through one or more conveyors. The next line contains an integer $k$ ($1 \leq k \leq 100 000$), which indicates the number of required transfers from a machine shop to another. Each of the following $k$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i \leq n$, $1 \leq b_i \leq n$, $a_i \ne b_i$), meaning that transfer from the machine shop $a_i$ to the machine shop $b_i$ is required. Either $a_i \ne a_j$ or $b_i \ne b_j$ holds for $i \ne j$.
Output “
3 2 1 2 2 3 3 1 2 1 3 2 3
Yes 1 2 2 3
3 2 1 2 2 3 3 1 2 1 3 3 2
No
4 4 1 2 1 3 1 4 2 3 7 1 2 1 3 1 4 2 1 2 3 3 1 3 2
Yes 1 2 2 3 3 1 1 4