For an undirected graph $G = \langle V, E \rangle$, its line graph $L(G)$ is also an undirected graph:

• Its vertex set has size $|E|$, where each vertex corresponds uniquely to an edge in the original graph.
• Two vertices are connected by an edge if and only if their corresponding edges in the original graph share a common endpoint (note that there are no self-loops).

Now, given a simple undirected graph $G$ with $n$ vertices and $m$ edges (not necessarily connected), you need to construct a simple undirected graph $H$ with $n'$ vertices and $n$ edges such that $L(H) = G$.

Input

The input contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases. For each test case:

The first line contains two integers $n, m$.

The next $m$ lines each contain two integers $u, v$, describing an edge.

It is guaranteed that $\sum n \leq 3 \times 10^5$ and $\sum m \leq 3 \times 10^6$.

Output

For each test case, if no such $H$ exists, output a single line containing No.

Otherwise, output a single line containing Yes, followed by a line containing two integers $n', m'$, representing the number of vertices and edges of $H$, respectively.

The next $m'$ lines each contain two integers $u, v$, describing an edge.

You must ensure $1 \leq n' \leq 10^6$ and $m'=n$, and the edges must be output in the order of the vertex indices.

If there are multiple valid outputs, you may output any one of them.

Examples

Input 1

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

Output 1

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

Examples 2-11

See the provided files. These samples satisfy the special constraints of their respective subtasks.

Subtasks

For all data, $1 \leq n, \sum n \leq 3 \times 10^5$, $0 \leq m, \sum m \leq 3 \times 10^6$, $1 \leq T \leq 3 \times 10^5$.

Additional notes:

• (Property A): It is guaranteed that all test cases have a solution, and there exists a graph $H$ satisfying the requirements such that $H$ is a tree.