在图论的数学学科中，无向图 $G$ 的线图 $L(G)$ 是另一个表示 $G$ 中边之间邻接关系的图。$L(G)$ 的构造方式如下：对于 $G$ 中的每一条边，在 $L(G)$ 中创建一个顶点；对于 $G$ 中任意两条有公共顶点的边，在 $L(G)$ 中它们对应的顶点之间连一条边。（摘自维基百科）

线图构造示例

你已经解决过许多基于线图的任务，但你非常喜欢线图，以至于你想再解决一个任务！

给定一个包含 $n$ 个顶点和 $m$ 条边的简单无向图 $G$。你的任务是找到另一个简单无向图 $H$，使得 $G$ 是 $H$ 的线图。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 3 \cdot 10^5$)，表示测试用例的数量。接下来是各测试用例的输入：

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^6$)，表示图 $G$ 中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示 $G$ 中顶点 $u$ 和顶点 $v$ 之间的一条无向边。

保证 $1 \le \sum n \le 3 \cdot 10^5$ 且 $0 \le \sum m \le 3 \cdot 10^6$，且给定的图不包含重边或自环。

输出格式

对于每个测试用例，如果不存在这样的图 $H$，输出一行 “No”。

否则，输出一行 “Yes”，接着输出一行，包含两个整数 $n'$ 和 $m'$ ($0 \le n' \le 10^6, m' = n$)，表示 $H$ 的顶点数和边数。

接下来的 $m'$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n', u \neq v$)，表示 $H$ 中顶点 $u$ 和顶点 $v$ 之间的一条无向边。

注意，$H$ 中的边将按照你输出的顺序编号为 $1, 2, \dots, m'$。你需要确保边的编号与 $G$ 中顶点的编号一一对应。

如果存在多种可能的解，你可以输出其中任意一个。

样例

输入 1

6
5 6
1 2
1 3
1 4
3 4
2 5
4 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
5 5
3 4
1 3
4 5
2 4
1 2
Yes
2 1
1 2
Yes
3 2
2 3
1 2
Yes
4 3
2 3
2 4
1 2
No
Yes
5 5
4 5
3 4
1 3
2 3
1 2