Given an undirected connected graph with vertices and edges, your task is to find a spanning tree of the graph such that for every vertex in the spanning tree its degree is not larger than .

Recall that the degree of a vertex is the number of edges it is connected to.

输入描述:

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:

The first line contains two integers  and  (, ) indicating the number of vertices and edges in the graph.

For the following  lines, the -th line contains two integers  and  () indicating that there is an edge connecting vertex  and . Please note that there might be self loops or multiple edges.

It's guaranteed that the given graph is connected. It's also guaranteed that the sum of  of all test cases will not exceed , also the sum of  of all test cases will not exceed .

输出描述:

For each test case, if such spanning tree exists first output "Yes" (without quotes) in one line, then for the following  lines print two integers  and  on the -th line separated by one space, indicating that there is an edge connecting vertex  and  in the spanning tree. If no valid spanning tree exists just output "No" (without quotes) in one line.

2
6 9
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 6
3 4
1 3
2 3
3 3
1 2

Yes
1 2
1 3
1 4
4 5
4 6
No

备注:

For the first sample test case, the maximum degree among all vertices in the spanning tree is 3 (both vertex 1 and vertex 4 has a degree of 3). As  this is a valid answer.

For the second sample test case, it's obvious that any spanning tree will have a vertex with degree of 2, as  no valid answer exists.