← 返回题目列表

AtCoder · abc320_d

G. 相对位置

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 人数 1 to N 。
人 1 位于原点。

你被给予 M 信息的形式如下:

  • 来自人 A_i的观点、人 B_i is X_i 单位距离为正 x- 方向和 Y_i 单位距离为正 y- 方向。

确定每个人的坐标。如果无法唯一确定某个人的坐标,请报告该事实。

约束

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1\leq A_i, B_i \leq N
  • A_i \neq B_i
  • -10^9 \leq X_i,Y_i \leq 10^9
  • 所有输入值均为整数。
  • 给出的信息是一致的。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 X_1 Y_1
\vdots
A_M B_M X_M Y_M

输出

打印 N 行。
如果人的坐标 i 无法唯一确定, i- 第行应包含 undecidable.
如果它们可以唯一确定为 (s_i,t_i), i- 第行应包含 s_i 和 t_i 按此顺序,用空格分隔。


示例输入 1

3 2
1 2 2 1
1 3 -1 -2

示例输出 1

0 0
2 1
-1 -2

下图是三人的位置关系。

Figure


示例输入 2

3 2
2 1 -2 -1
2 3 -3 -3

示例输出 2

0 0
2 1
-1 -2

下图是三人的位置关系。

Figure


示例输入 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

示例输出 3

0 0
0 0
0 0
undecidable
undecidable

同一条信息可能会被多次给出,并且多个人可能在同一坐标处。