Nông dân John dự định xây dựng \(N\) trang trại (\(1 \leq N \leq 10^5\)) được nối với nhau bằng \(N-1\) con đường, tạo thành một cây (tức là mọi trang trại đều có thể đi đến nhau và không có chu trình). Mỗi trang trại có một cô bò với kiểu là một số nguyên \(T_i\) từ \(1\) đến \(N\), kể cả hai đầu mút.

\(M\) người bạn của Nông dân John (\(1 \leq M \leq 10^5\)) thường đến thăm ông. Trong chuyến thăm của người bạn \(i\), Nông dân John sẽ cùng người bạn đi dọc theo đường đi duy nhất từ trang trại \(A_i\) đến trang trại \(B_i\) (có thể xảy ra trường hợp \(A_i=B_i\)). Ngoài ra, họ có thể nếm sữa của bất kỳ cô bò nào dọc theo đường đi. Vì phần lớn bạn bè của Nông dân John cũng là nông dân, họ có sở thích rất khắt khe về sữa. Mỗi người bạn chỉ uống sữa từ một kiểu bò nhất định. Mỗi người bạn của Nông dân John chỉ vui nếu có thể uống loại sữa mình ưa thích trong chuyến thăm.

Hãy xác định liệu mỗi người bạn có vui sau chuyến thăm hay không.

Phân nhóm

• Test 2 là ví dụ thứ hai bên dưới.
• Test 3 thỏa mãn \(N \leq 10^3\), \(M \leq 2\cdot 10^3\).
• Các test 4–7 thỏa mãn \(C_i \leq 10\) (\(C_i\) được định nghĩa bên dưới).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

Dòng thứ hai chứa \(N\) số nguyên \(T_1,T_2,\ldots,T_N\), cách nhau bởi dấu cách. Kiểu của cô bò ở trang trại thứ \(i\) được biểu thị bằng \(T_i\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên phân biệt \(X\) và \(Y\) (\(1 \leq X,Y \leq N\)), cho biết có một cạnh giữa trang trại \(X\) và trang trại \(Y\).

\(M\) dòng tiếp theo chứa các số nguyên \(A_i\), \(B_i\) và \(C_i\). \(A_i\) và \(B_i\) biểu thị hai đầu mút của đường đi trong chuyến thăm của người bạn \(i\), còn \(C_i\) (\(1 \leq C_i \leq N\)) cho biết kiểu bò có sữa mà người bạn đó thích uống.

Dữ liệu ra

In một xâu nhị phân độ dài \(M\). Ký tự thứ \(i\) của xâu phải là 1 nếu người bạn thứ \(i\) sẽ vui, hoặc là 0 nếu không.

Ví dụ

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

10110

6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4

0110

Nguồn

USACO 2019 December Contest, Gold - Milk Visits: https://usaco.org/index.php?page=viewproblem2&cpid=970

Tác giả: Spencer Compton.