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ò, thuộc giống Guernsey hoặc Holstein.

\(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ột số người bạn chỉ uống sữa Guernsey, còn những người còn lại chỉ uống sữa Holstein. 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

• Các test 2–5 thỏa mãn \(N \leq 10^3\), \(M \leq 2\cdot 10^3\).

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 một xâu độ dài \(N\). Ký tự thứ \(i\) của xâu là G nếu cô bò ở trang trại thứ \(i\) thuộc giống Guernsey, hoặc là H nếu cô bò ở trang trại thứ \(i\) thuộc giống Holstein.

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 con đường 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à một ký tự \(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\) là G hoặc H tùy theo người bạn thứ \(i\) thích sữa Guernsey hay sữa Holstein.

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
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

10110

Nguồn

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

Tác giả: Spencer Compton.