分数: 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
下图是三人的位置关系。

示例输入 2
3 2 2 1 -2 -1 2 3 -3 -3
示例输出 2
0 0 2 1 -1 -2
下图是三人的位置关系。

示例输入 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
同一条信息可能会被多次给出,并且多个人可能在同一坐标处。