E. Directing the Roads of Grafolandia
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In Grafolandia, there are $$$n$$$ cities connected by $$$m$$$ bidirectional roads, such that it is possible to reach any city from any other by passing through one or more roads. To reduce traffic, the government has decided to make $$$k$$$ roads one-way, but they want to ensure that it is still possible to reach all other cities from each city.

Help the Grafolandian rulers determine if this is possible, and if so, specify which roads to select and the direction each road should take.

Input

The input begins with the number of cases $$$T$$$. Following this are $$$T$$$ cases, each consisting of a line with the integers $$$n$$$, $$$m$$$, and $$$k$$$, followed by $$$m$$$ lines, each containing two cities $$$u, v$$$, indicating that there is a road between cities $$$u$$$ and $$$v$$$. The cities are numbered from $$$0$$$ to $$$n-1$$$.

Output

If it is not possible, write "NO" (without quotes). If it is possible, write "SI" (without quotes), followed by $$$k$$$ lines. In each of the following $$$k$$$ lines, write two integers $$$u, v$$$ for which there was a road between the $$$u$$$-th and $$$v$$$-th cities, indicating that the road will go from city $$$u$$$ to city $$$v$$$. If there are multiple possible solutions, write any of them.

Scoring

$$$1 \leq T \leq 100$$$, $$$2 \leq n \leq 20000$$$, $$$1 \leq k \leq m \leq 10^5$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^6$$$.

19 points $$$n \leq 10, m \leq 20, k = m$$$. The sum of $$$n+m$$$ for all cases is less than $$$250$$$.

10 points $$$k = 2$$$.

21 points $$$n \leq 1000, m \leq 2000, k = m$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^4$$$.

13 points $$$n \leq 1000, m \leq 2000$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^4$$$.

14 points $$$k = m$$$.

23 points No additional restrictions.

Example
Input
2
6 6 4
0 1
1 2
1 4
2 3
3 4
3 5
6 6 5
0 1
1 2
1 4
2 3
3 4
3 5
Output
SI
1 2
4 1
2 3
3 4
NO