Фермер Джон построил \(N\) (\(1 \leq N \leq 10^5\)) ферм, соединённых
\(N-1\) дорогами, формируя дерево (то есть, каждая ферма достижима от любой другой,
и отсутствуют циклы). Каждая ферма содержит коров, чья марка Guernsey или
Holstein.
\(M\) друзей ФД (\(1 \leq M \leq 10^5\)) часто посещают его фермы. Во время
визита друга \(i\), ФД идёт с эти другом по уникальному маршруту от фермы \(A_i\)
до фермы \(B_i\) (возможен случай, когда \(A_i = B_i\)). Дополнительно они могут
попробовать некоторое количество молока вдоль пути, по которому они идут.
Поскольку большинство друзей ФД сами фермеры, у них есть сильные предпочтения
по молоку. Некоторые из его друзей пьют молоко только коров Guernsey, а оставшиеся
пьют только молоко Holstein. Любой из друзей ФД будет счастлив только если
он сможет попить предпочитаемое молоко во время визита.
Определите, каждый ли друг останется счастлив после визита.
ОЦЕНИВАНИЕ:
- Тесты 2-5 удовлетворяют \(N\le 10^3, M\le 2\cdot 10^3.\)
ФОРМАТ ВВОДА (файл milkvisits.in):
Первая строка содержит два целых числа
\(N\) и
\(M\).
Вторая строка содержит строку длину длины \(N\). \(i\)-ый символ строки
есть 'G' если корова на \(i\)-ой ферме Guernsey, или 'H', если корова
на \(i\)-ой ферме Holstein.
Каждая их следующих \(N-1\) строк содержит два целых числа
\(X\) и \(Y\) (\(1 \leq X, Y \leq N\)), указывающих, что существует дорога между
фермами \(X\) и \(Y\).
Последующие \(M\) строк содержат целые числа \(A_i\), \(B_i\) и символ \(C_i\).
\(A_i\) и \(B_i\) представляют конечные точки пути \(i\)'-го друга, а \(C_i\)
либо G либо H - тип молока, предпочитаемый \(i\)-ым другом.
ФОРМАТ ВЫВОДА (файл milkvisits.out):
Выведите двоичную строку длины \(M\). \(i\)-ый символ строки должен быть
'1' если \(i\)-ый друг будет счастлив, или '0' в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|