对于无向图 $G = ⟨V, E⟩$，它的线图 $L(G)$ 也是一个无向图:

• 它的点集大小为 $E$，每个点唯一对应着原图的一条边。
• 两个点之间有边当且仅当这两个点对应的边在原图上有公共点(注意不会有自环)。

现在，给定一张 $n$ 个点 $m$ 条边的简单无向图 $G$ （不保证连通），你需要构造一张 $n'$ 个点 $n$ 条边的简单无向图 $H$，使得 $L(H) = G$。

输入格式

输入包含多组数据。

输入的第一行包含一个整数 $T$，表示数据组数。对于每组数据：

输入的第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $u,v$，描述一条边。

数据保证 $\sum n \leq 3 \times 10^5, \sum m \leq 3 \times 10^6$。

输出格式

对于每组数据，如果不存在对应的 $H$，则输出一行 No。

否则，输出一行 Yes，接下来一行包含两个整数 $n', m'$，分别表示 $H$ 的点数和边数。

接下来 $m'$ 行，每行两个整数 $u,v$，描述一条边。

你必须保证 $1 \leq n' \leq 10^6$ 且 $m'=n$，且边按照点的编号顺序来输出。

如果有多种合法的输出，你可以输出任何一种。

样例数据

样例 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

样例 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

样例 2

见下发文件。

本组样例满足子任务 2 的特殊限制。

样例 3

见下发文件。

本组样例满足子任务 3 的特殊限制。

样例 4

见下发文件。

本组样例满足子任务 4 的特殊限制。

样例 5

见下发文件。

本组样例满足子任务 5 的特殊限制。

样例 6

见下发文件。

本组样例满足子任务 6 的特殊限制。

样例 7

见下发文件。

本组样例满足子任务 7 的特殊限制。

样例 8

见下发文件。

本组样例满足子任务 8 的特殊限制。

样例 9

见下发文件。

本组样例满足子任务 9 的特殊限制。

样例 10

见下发文件。

本组样例满足子任务 10 的特殊限制。

样例 11

见下发文件。

本组样例满足子任务 11 的特殊限制。

子任务

对于所有数据，$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$。

下面是一些额外说明：

• （性质 A）：保证所有数据均有解，且存在一张符合要求的图 $H$ 满足 $H$ 是一棵树。

时间限制：$\texttt{10s}$

空间限制：$\texttt{2048MB}$