题目描述

给定一棵包含 $N$ 个结点的树，其中 $N$ 为奇数。结点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接结点 $u_i$ 和 $v_i$，且具有两个整数权值：初始权值 $w_{i,1}$ 和目标权值 $w_{i,2}$。

你可以执行任意多次（包括零次）以下操作：

• 选择一条边 $(u,v)$，当前权值为 $w$。将所有恰与 $u,v$ 中一个点相连的边的权值异或上 $w$（不包括 $(u,v)$ 这条边本身）。

判断能否通过执行上述操作（任意顺序，任意次数），使得对于每一条边 $i$，其权值从初始的 $w_{i,1}$ 变为目标值 $w_{i,2}$。

输入格式

第一行一个正整数 $N$，表示树的结点个数。

下面 $N-1$ 行，每行四个非负整数 $u_i,v_i,w_{i,1},w_{i,2}$，表示树上的一条边。

输出格式

如果有可能通过操作使所有边的权值变为目标值，输出一行 YES；否则输出一行 NO。

样例 1

输入

3
1 2 1 1
2 3 8 9

输出

YES

样例 2

输入

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

输出

NO

说明/提示

样例一解释

如果操作边 $(1,2)$，那么边 $(2,3)$ 的权值会变成 $8\oplus 1=9$。

数据范围

• $1 \le N \le 10^5$
• $1 \le u_i, v_i \le N$ (保证输入构成一棵树)
• $0 \le w_{i,1} < 2^{30}$
• $0 \le w_{i,2} < 2^{30}$

翻译部分由 Deepseek R1 大模型提供。