There are $n$ islands scattered in the sea, with $m$ bidirectional shipping routes between them. The $i$-th ($1 \le i \le m$) route connects islands $u_i$ and $v_i$, and there is a ferry operating back and forth on this route.

Each ferry has an initial docking position. For the ferry on the $i$-th route: If $w_i = 0$, the ferry is initially docked at island $u_i$. If $w_i = 1$, you can choose for the ferry to be initially docked at either island $u_i$ or island $v_i$.

There are $k$ travelers. The $j$-th ($1 \le j \le k$) traveler is initially located at island $s_j$ and needs to travel to island $t_j$. Travelers can only move via ferries. Specifically, each move involves choosing a traveler $j$ ($1 \le j \le k$) and a route $i$ ($1 \le i \le m$) such that traveler $j$ and the ferry on route $i$ are currently at the same island. The traveler then boards the ferry and moves with it to the island at the other end of route $i$. For example, if both traveler $j$ and the ferry on route $i$ are at island $u_i$, after the move, both will arrive at island $v_i$, and vice versa.

You need to determine whether it is possible to reach the destination for all travelers through a series of moves. If it is possible, you must also provide a specific sequence of moves.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file ferry.h by adding the following code at the beginning of your program:

#include "ferry.h"

You must implement the following function in your source file:

void ferry(int n, int m, int k, std::vector<int> u,
           std::vector<int> v, std::vector<int> w, std::vector<int> s,
           std::vector<int> t);

• $n, m, k$ represent the number of islands, the number of routes, and the number of travelers, respectively.
• For $0 \le i < m$, $u_i, v_i$ represent the two islands connected by the $(i+1)$-th route, and $w_i$ indicates whether the initial docking position of the ferry on that route is fixed (see the description above).
• For $0 \le j < k$, $s_j, t_j$ represent the initial island and the destination island of the $(j+1)$-th traveler.
• For each test case, this function will be called exactly once by the interactor.

You can report whether it is possible for all travelers to reach their respective destinations by calling the following function:

void report(bool o);

• If $o$ is true, it means it is possible for all travelers to reach their destinations; if $o$ is false, it means it is not.

You must ensure that the ferry function is called exactly once by the interactor.

You can perform a move by calling the following function:

void move(int j, int i);

• $j$ and $i$ represent the indices of the chosen traveler and the route, respectively, as defined in the description. You must ensure $1 \le j \le k$, $1 \le i \le m$, and that traveler $j$ and the ferry on route $i$ are currently at the same island. Specifically, if the initial docking position of the ferry on route $i$ is not yet determined, and traveler $j$ is at one of the islands connected by route $i$, the initial docking position of the ferry on route $i$ is immediately determined to be the island where traveler $j$ is located.
• You must ensure that for each call to ferry, the number of calls to this function does not exceed $10^6$, and all calls to this function occur after the report function is called, and the return value of the report function must be true.

Note: In any case, the execution time of the interactor will not exceed 0.1 seconds, and the memory used is fixed and will not exceed 64 MiB.

Examples

Input 1

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

Output 1

Yes
4
2 5
2 3
1 1
1 3

Note 1

• Initially, traveler 1 is at island 1, and traveler 2 is at island 4.
• After the first move, traveler 2 and the ferry on route 5 move to island 3.
• After the second move, traveler 2 and the ferry on route 3 move to island 2.
• During the third move, the initial docking position of the ferry on route 1 is determined to be island 1; after the move, traveler 1 and the ferry on route 1 arrive at island 2.
• After the fourth move, traveler 1 and the ferry on route 3 move to island 3.

Subtasks

For all test data: $2 \le n \le 2,000$, $1 \le m \le 10^4$, $1 \le k \le 10^2$; For all $1 \le i \le m$, $1 \le u_i, v_i \le n$, $u_i \neq v_i$, $w_i \in \{0, 1\}$; * For all $1 \le i \le k$, $1 \le s_i, t_i \le n$.

Scoring

Note: You should not obtain internal information of the interactor through illegal means, such as interacting directly with standard input/output streams. Such behavior will be considered cheating. The final evaluation interactor is different from the sample interactor.

This problem is subject to the same constraints as traditional problems; for example, compilation errors will result in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test case. You may only access variables defined within your program and variables provided by the interactor; attempting to access other memory spaces may result in compilation or runtime errors.

Each time the ferry function is called, if the report or move function is called illegally, or if the move function is called more than $10^6$ times, the corresponding test case will receive 0 points.

Based on the above conditions: * For each test case, if the return value of the report function is correct, you can receive 40% of the points; on this basis, if the report return value is false, or if all travelers have reached their respective destination islands when the ferry function returns, you can receive full marks.