#P17892. Manhattan Graph
Manhattan Graph
Manhattan Graph
给定一个无向连通图,含 个顶点和 条边。请将每个顶点 放在二维平面的一个整数格点 上,使任意两点之间的图上最短路长度等于它们的曼哈顿距离:
这里图上每条边长为 。因此相邻顶点必须放在横向或纵向相邻的格点,不同顶点不能重合。
如果存在这样的放置方式,输出任意一种;否则报告无解。
输入格式
第一行测试用例数 ,。
每组第一行两个整数 ,,。
接下来 行各包含两个整数 ,表示无向边,,。保证图连通。
所有测试用例的 之和、 之和均不超过 。
原始输入在每组数据前可以有一个空行,读入时忽略即可。
输出格式
无解时输出一行 NO。
有解时先输出一行 YES,随后输出 行,每行两个整数 ,要求 。
若有多种合法放置方式,输出任意一种。
样例
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