Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Цепные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Изначально все вершины окрашены в белый или черный цвет.

Вам предлагается выполнить $$$q$$$ запросов:

  • «u» — поменять цвет вершины $$$u$$$ (если она была белой, то поменять на черную и наоборот).

После каждого запроса вы должны ответить, образуют ли все черные вершины цепочку. То есть существуют ли две черные вершины такие, что простой путь между ними проходит через все черные вершины и только через черные вершины. В частности, если существует только одна черная вершина, то она образует цепочку. Если черных вершин нет, то они не образуют цепочку.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1\leq n,q\leq 2\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1,c_2,\ldots,c_n$$$ ($$$c_i \in \{ \mathtt{0}, \mathtt{1} \}$$$) — изначальные цвета вершин. $$$c_i$$$ обозначает цвет вершины $$$i$$$, где $$$\mathtt{0}$$$ обозначает белый цвет, а $$$\mathtt{1}$$$ — черный.

Далее следует $$$n - 1$$$ строка, каждая из которых содержит по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i,y_i \le n$$$), обозначающих ребро между вершинами $$$x_i$$$ и $$$y_i$$$. Гарантируется, что эти ребра образуют дерево.

Следующие $$$q$$$ строк содержат по одному целому числу $$$u_i$$$ ($$$1 \le u_i \le n$$$), указывающему на то, что цвет вершины $$$u_i$$$ необходимо поменять.

Гарантируется, что и сумма $$$n$$$, и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$2\cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите «Yes», если черные вершины образуют цепочку, и «No» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Примеры
Входные данные
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
Входные данные
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
Примечание

Во втором наборе входных данных цвета вершин следующие:

Исходное дерево:

Первый запрос меняет цвет вершины $$$4$$$:

Второй запрос меняет цвет вершины $$$3$$$:

Третий запрос меняет цвет вершины $$$2$$$:

Четвертый запрос меняет цвет вершины $$$5$$$: