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