#P17892. Manhattan Graph

Manhattan Graph

Manhattan Graph

给定一个无向连通图,含 nn 个顶点和 mm 条边。请将每个顶点 ii 放在二维平面的一个整数格点 pi=(xi,yi)p_i=(x_i,y_i) 上,使任意两点之间的图上最短路长度等于它们的曼哈顿距离:

dist⁡(i,j)=∣xi−xj∣+∣yi−yj∣.\operatorname{dist}(i,j)=|x_i-x_j|+|y_i-y_j|.

这里图上每条边长为 11。因此相邻顶点必须放在横向或纵向相邻的格点,不同顶点不能重合。

如果存在这样的放置方式,输出任意一种;否则报告无解。

输入格式

第一行测试用例数 tt,1≤t≤500001\le t\le50000。

每组第一行两个整数 n,mn,m,1≤n≤5000001\le n\le500000,n−1≤m≤500000n-1\le m\le500000。

接下来 mm 行各包含两个整数 u,vu,v,表示无向边,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。保证图连通。

所有测试用例的 nn 之和、mm 之和均不超过 500000500000。

原始输入在每组数据前可以有一个空行,读入时忽略即可。

输出格式

无解时输出一行 NO。

有解时先输出一行 YES,随后输出 nn 行,每行两个整数 xi,yix_i,y_i,要求 −998244353≤xi,yi≤998244353-998244353\le x_i,y_i\le998244353。

若有多种合法放置方式,输出任意一种。

样例

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

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
NO
NO