AT_abc320_d [ABC320D] Relative Position

题目描述

在一个平面直角坐标系上有 $n$ 个点，每个点有编号，它们间存在 $m$ 条关系，其中第 $i$ 条关系格式如下：

• 给定编号 $a_i,b_i$ 与整数 $x_i,y_i$，表示若第 $a_i$ 个点的坐标为 $(p_i,q_i)$，则满足第 $b_i$ 个点的坐标为 $(p_i+x_i,q_i+y_i)$。保证 $a_i\not =b_i$。

其中 $1$ 号点的坐标为 $(0,0)$。

你需要根据这些关系求出每个点的坐标，或输出 undecidable 以报告其中一些点的坐标无法确定。保证关系不会互相矛盾，但可能重复。

$1\le a_i,b_i\le n\le 2\times10^5$，$0\le m\le 2\times 10^5$，$-10^9\le x_i,y_i\le 10^9$。

输入格式

第一行包含两个整数 $n,m$，含义同题面。

接下来 $m$ 行，第 $i$ 行包含四个整数 $a_i,b_i,x_i,y_i$。

输出格式

输出共 $n$ 行，第 $i$ 行输出用空格分隔的两个整数表示第 $i$ 个点的坐标，若该点坐标无法确定则输出 undecidable。

输入输出样例 #1

输入 #1

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

输出 #1

0 0
2 1
-1 -2

输入输出样例 #2

输入 #2

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

输出 #2

0 0
2 1
-1 -2

输入输出样例 #3

输入 #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

存在重复给出相同信息、或多人处于同一坐标的情况。

说明/提示

制約

• $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$
• 输入均为整数
• 输入信息无矛盾