Lucy 正在为 Xeppelin 竞赛准备插图。对于其中一个问题，她需要画一个图。问题在于，画出一张好看的图并不容易。

Lucy 认为，在方格纸上绘制一个含有 $n$ 个顶点和 $m$ 条边的无向连通图是最好的选择。图的每个顶点都将是网格中的一个整点 $(x, y)$，每条边都将是连接 $(x, y) \leftrightarrow (x + 1, y)$ 或 $(x, y) \leftrightarrow (x, y + 1)$ 的线段（对于某些整数 $x$ 和 $y$）。她只需要高亮显示方格图案的某些部分，插图就完成了！

然而，如果绘制的图能够保持原图中的距离，那就更好了。正式地，考虑二维平面上的整点。一个绘制方案是一个由 $n$ 个此类点组成的数组 $p_1, \dots, p_n$。如果对于所有可能的 $i$ 和 $j$，都有 $\text{dist}(i, j) = \text{Manhattan}(p_i, p_j)$，则称该绘制方案是美妙的（nice）。这里，$\text{dist}(u, v)$ 定义为图中顶点 $u$ 和 $v$ 之间最短路径上的边数，而 $\text{Manhattan}(p_i, p_j)$ 定义为平面上两个整点 $p_i$ 和 $p_j$ 之间的曼哈顿距离。

为给定的图找到一个美妙的绘制方案，或者指出它不存在。

输入格式

每个测试文件包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 50\,000$)。接下来的内容是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$)：图的顶点数和边数。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$, $u \ne v$)：表示图的一条边连接的两个顶点。保证图是连通的。

所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $500\,000$。

为了便于视觉观察，每个测试用例之前都有一个空行。它可以被忽略。

输出格式

对于每个测试用例，如果不存在美妙的绘制方案，则在单行中输出 "NO"。

否则，在第一行输出 "YES"。之后，输出一个美妙绘制方案的示例。接下来的 $n$ 行中，每行应包含两个整数 $x_i$ 和 $y_i$：第 $i$ 个点的坐标（$-998\,244\,353 \le x_i, y_i \le 998\,244\,353$）。如果有多个可能的答案，输出其中任意一个即可。

样例

输入样例 1

3

4 4
1 2
2 3
3 4
4 1

5 4
1 2
1 3
1 4
1 5

7 8
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7

输出样例 1

YES
0 0
1 0
1 1
0 1
YES
3 1
2 1
3 0
4 1
3 2
YES
1 2
2 2
1 3
2 3
3 3
2 4
3 4

输入样例 2

2

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

12 16
1 2
1 3
2 4
3 4
3 5
4 6
5 6
6 7
4 8
7 8
7 9
8 10
9 10
8 11
10 12
11 12

输出样例 2

NO
NO