#P17860. [XV Open Cup]Mosaic Tracery

[XV Open Cup]Mosaic Tracery

题目描述

整数网格上有一个由若干单位正方形组成的图案。所有正方形的边都平行于坐标轴,顶点坐标都是整数。

这些正方形通过公共边连成一体:可以从任意一个正方形出发,每次走到与当前正方形有公共边的另一个正方形,最终到达图案中的任意正方形。图案可以有孔洞。

将图案中所有正方形的顶点去重,得到 NN 个点,并任意编号为 11 到 NN。将所有正方形的边去重,得到 MM 条线段。现在只给出每条线段两个端点的编号,原来的坐标已经丢失。

请为这 NN 个点重新分配整数坐标,使所有点互不重合,并使输入中每条线段的两个端点在网格中相邻。

保证输入确实来自一个满足上述条件的图案。旋转、镜像、平移后的答案均可接受。

输入格式

第一行包含两个整数 N,MN,M。

接下来 MM 行,每行包含两个整数 Ui,ViU_i,V_i,表示一条线段的两个端点。输入无自环、无重复边,边无方向。

输出格式

输出 NN 行。第 jj 行包含两个整数 Xj,YjX_j,Y_j,表示编号为 jj 的点的坐标。

输出必须满足:

  1. −100000≤Xj,Yj≤100000-100000\le X_j,Y_j\le100000;
  2. 任意两个点的坐标不同;
  3. 对输入的每条边 (u,v)(u,v),有 ∣Xu−Xv∣+∣Yu−Yv∣=1|X_u-X_v|+|Y_u-Y_v|=1。

如果存在多个答案,输出任意一个。判题只要求输入中的边满足上述条件,不额外要求未列出的点对不能在输出中相邻。

数据范围

  • 4≤N≤1000004\le N\le100000;
  • 1≤Ui,Vi≤N1\le U_i,V_i\le N;
  • MM 由合法图案决定。每个点的度数至多为 44,因而 M≤2NM\le2N。

样例

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

样例解释

四个点构成一个单位正方形。本样例为便于阅读而新增的等价示例。