Вам дано дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\). Изначально все вершины окрашены в белый или черный цвет.
Вам предлагается выполнить \(q\) запросов:
- «u» — поменять цвет вершины \(u\) (если она была белой, то поменять на черную и наоборот).
После каждого запроса вы должны ответить, образуют ли все черные вершины цепочку. То есть существуют ли две черные вершины такие, что простой путь между ними проходит через все черные вершины и только через черные вершины. В частности, если существует только одна черная вершина, то она образует цепочку. Если черных вершин нет, то они не образуют цепочку.
Выходные данные
Для каждого запроса выведите «Yes», если черные вершины образуют цепочку, и «No» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Во втором наборе входных данных цвета вершин следующие:
Исходное дерево:
Первый запрос меняет цвет вершины \(4\):
Второй запрос меняет цвет вершины \(3\):
Третий запрос меняет цвет вершины \(2\):
Четвертый запрос меняет цвет вершины \(5\):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
1 0
1 2
1
5 4
1 0 0 0 0
1 2
1 3
1 5
3 4
4
3
2
5
|
No
No
Yes
Yes
No
|
|
2
|
4
5 3
1 1 1 1 1
3 5
2 5
3 4
1 5
1
1
1
4 4
0 0 0 0
1 2
2 3
1 4
1
2
3
2
1 1
1
1
1 1
0
1
|
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
|