atcoder#AGC052B. [AGC052B] Tree Edges XOR

[AGC052B] Tree Edges XOR

Score : 800800 points

Problem Statement

You are given a tree with NN vertices, where NN is odd. The vertices are numbered from 11 through NN and edges from 11 through N1N-1. The edge ii connects vertices uiu_i and viv_i and its initial weight is wi1w^1_i.

You can perform the following operation any number of times:

  • Choose an edge (u,v)(u, v) of the tree, and suppose that its weight now is ww. For every edge, which is incident to exactly one of uu and vv, we XOR the weight of that edge with ww (if it was w1w_1, replace it with w1ww_1 \oplus w).

Your goal is to reach the state where each edge ii has weight wi2w^2_i. Determine if you can get to the goal by performing the operation above any number of times.

Constraints

  • 1N1051 \le N \le 10^5
  • NN is odd.
  • 1ui,viN1\le u_i, v_i \le N
  • uiviu_i \neq v_i
  • 0wi1,wi2<2300\le w^1_i, w^2_i < 2^{30}
  • All values in input are integers.
  • The input represents a valid tree.

Input

Input is given from Standard Input in the following format:

NN

u1u_1 v1v_1 w11w^1_1 w12w^2_1

u2u_2 v2v_2 w21w^1_2 w22w^2_2

\vdots

uN1u_{N-1} vN1v_{N-1} wN11w^1_{N-1} wN12w^2_{N-1}

Output

If you can get the goal weight assignment from the initial state, output YES. Otherwise, output NO. Note that the checker is case-insensitive: you can print letters in both uppercase and lowercase.

3
1 2 1 1
2 3 8 9
YES

If you perform the operation on the edge 11, the weight of the edge 22 becomes 81=98 \oplus 1=9.

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