Определим мажорирующий элемент последовательности из \(k\) элементов как уникальное значение, которое появляется строго более чем \(\left \lfloor {\frac{k}{2}} \right \rfloor\) раз. Если такое значение не существует, то последовательность не имеет мажорирующего элемента. Например, последовательность \([1,3,2,3,3]\) имеет мажорирующий элемент \(3\), потому что оно появляется \(3 > \left \lfloor {\frac{5}{2}} \right \rfloor = 2\) раза, но \([1,2,3,4,5]\) и \([1,3,2,3,4]\) не имеют мажорирующего элемента.
Скибидус нашел дерево\(^{\text{∗}}\) из \(n\) вершин и массив \(a\) длиной \(n\). Вершина \(i\) имеет значение \(a_i\), написанное на ней, где \(a_i\) — это целое число в диапазоне \([1, n]\).
Для каждого \(i\) от \(1\) до \(n\) определите, существует ли нетривиальный простой путь\(^{\text{†}}\) такой, что \(i\) является мажорирующим элементом последовательности целых чисел, написанных на вершинах, которые образуют путь.
Выходные данные
Для каждого теста выведите двоичную строку \(s\) длиной \(n\) на отдельной строке. \(s_i\) должно вычисляться следующим образом:
- Если существует нетривиальный путь, содержащий \(i\) как мажорирующий элемент, то \(s_i\) равно '1';
- В противном случае \(s_i\) равно '0'.
Примечание
В первом примере нет нетривиального пути с \(1\), \(2\) или \(3\) в качестве мажорирующего элемента, поэтому выводимая двоичная строка — «000».
Во втором примере \(1\rightarrow 2\rightarrow 4\) — это нетривиальный путь с \(3\) в качестве мажорирующего элемента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
1 3
2 3
4
3 1 1 3
1 2
2 3
4 2
4
2 4 4 2
1 2
2 3
3 4
13
1 4 4 7 4 7 1 1 7 11 11 11 11
1 2
2 3
3 4
4 5
4 6
2 7
7 8
2 9
6 10
5 11
11 12
10 13
|
000
1010
0001
1001001000100
|