트리 접기

다다스는 빨간색과 파란색 간선으로 이루어진 트리를 접는 놀이를 하고 있다.

정점이 $N$개인 두 트리 $T_1, T_2$가 주어진다. 각 간선은 빨간색 또는 파란색으로 칠해져 있다. 색은 입력에서 $0$ 또는 $1$로 주어진다.

하나의 트리에서 다음 연산을 접기 연산이라고 한다.

어떤 정점 $a$에 대해, 간선 $(a,b)$와 $(a,c)$가 모두 존재하고 두 간선의 색이 같다면, 정점 $b$와 정점 $c$를 하나의 정점으로 병합할 수 있다. 병합 후 중복 간선은 하나로 합쳐진다.

두 트리 $X,Y$가 닮았다는 것은 다음 조건을 만족한다는 뜻이다.

$X$에 접기 연산을 $0$번 이상 적용하여 $X'$를 만들고, $Y$에 접기 연산을 $0$번 이상 적용하여 $Y'$를 만들었을 때, $X'$와 $Y'$가 완전히 같아지도록 만들 수 있다. 단, 한쪽 트리의 모든 간선 색을 반전한 뒤 같아지는 경우도 같다고 본다 (정점 번호는 무시함에 주의하라).

트리 $T$와 정수 $l,r$ $(1 \le l \le r \le N)$에 대해, $T[l \dots r]$을 정점 $l,l+1,\ldots,r$을 모두 포함하는 $T$의 최소 연결 부분트리라고 하자.

$Q$개의 쿼리가 주어진다. 각 쿼리는 네 정수 $l_1,r_1,l_2,r_2$로 이루어진다.

각 쿼리에 대해, $T_1[l_1 \dots r_1]$과 $T_2[l_2 \dots r_2]$가 닮았는지 판별하라.

입력은 다음과 같은 형식으로 주어진다.

$N \ Q$ $U_1 \ V_1 \ W_1$ $U_2 \ V_1 \ W_1$ $\vdots$ $U_{N-1} \ V_{N-1} \ W_{N-1}$ $X_1 \ Y_1 \ Z_1$ $X_2 \ Y_2 \ Z_2$ $\vdots$ $X_{N-1} \ Y_{N-1} \ Z_{N-1}$ $\text{query}_1$ $\text{query}_2$ $\vdots$

$\text{query}_Q$

이는 각 $i \ (1 \leq i \leq N-1)$에 대해 $T_1$에 $U_i$와 $V_i$를 잇는 색 $W_i$의 간선이 존재하고, $T_2$에 $X_i$와 $Y_i$를 잇는 색 $Z_i$의 간선이 존재함을 의미한다. 색은 $0$이면 빨간색, $1$이면 파란색이다.

각각의 $\text{query}_i$ ($1 \leq i \leq Q$)의 형식은 다음과 같다.

$l_1 \ r_1 \ l_2 \ r_2$

각각의 쿼리마다, 두 부분트리가 닮았다면 YES, 아니라면 NO를 한 줄에 하나씩 출력한다.

• $1 \leq N \leq 200 \ 000$.
• $1 \leq Q \leq 200 \ 000$.
• $1 \leq U_i \leq N$ ($1 \leq i \leq N-1$).
• $1 \leq V_i \leq N$ ($1 \leq i \leq N-1$).
• $U_i \neq V_i$ ($1 \leq i \leq N-1$).
• $W_i \in \{0, 1\}$ ($1 \leq i \leq N-1$).
• $1 \leq X_i \leq N$ ($1 \leq i \leq N-1$).
• $1 \leq Y_i \leq N$ ($1 \leq i \leq N-1$).
• $X_i \neq Y_i$ ($1 \leq i \leq N-1$).
• $Z_i \in \{0, 1\}$ ($1 \leq i \leq N-1$).
• 각 간선은 트리를 이룸이 보장된다.

모든 쿼리는 다음 조건을 만족한다.

• $1 \leq l_1 \leq N$.
• $1 \leq r_1 \leq N$.
• $l_1 \leq r_1$.
• $1 \leq l_2 \leq N$.
• $1 \leq r_2 \leq N$.
• $l_2 \leq r_2$.