#P17860. [XV Open Cup]Mosaic Tracery
[XV Open Cup]Mosaic Tracery
题目描述
整数网格上有一个由若干单位正方形组成的图案。所有正方形的边都平行于坐标轴,顶点坐标都是整数。
这些正方形通过公共边连成一体:可以从任意一个正方形出发,每次走到与当前正方形有公共边的另一个正方形,最终到达图案中的任意正方形。图案可以有孔洞。
将图案中所有正方形的顶点去重,得到 个点,并任意编号为 到 。将所有正方形的边去重,得到 条线段。现在只给出每条线段两个端点的编号,原来的坐标已经丢失。
请为这 个点重新分配整数坐标,使所有点互不重合,并使输入中每条线段的两个端点在网格中相邻。
保证输入确实来自一个满足上述条件的图案。旋转、镜像、平移后的答案均可接受。
输入格式
第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示一条线段的两个端点。输入无自环、无重复边,边无方向。
输出格式
输出 行。第 行包含两个整数 ,表示编号为 的点的坐标。
输出必须满足:
- ;
- 任意两个点的坐标不同;
- 对输入的每条边 ,有 。
如果存在多个答案,输出任意一个。判题只要求输入中的边满足上述条件,不额外要求未列出的点对不能在输出中相邻。
数据范围
- ;
- ;
- 由合法图案决定。每个点的度数至多为 ,因而 。
样例
4 4
1 2
2 3
3 4
4 1
0 0
1 0
1 1
0 1
样例解释
四个点构成一个单位正方形。本样例为便于阅读而新增的等价示例。