H1. Кевин и камни (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно только определить, существует ли корректная последовательность операций. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Кевина есть неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Изначально некоторые вершины содержат камни, которые Кевин хочет переместить на новые позиции.

Кевин может выполнять следующую операцию:

  • Для каждого камня на $$$u_i$$$ выбрать соседнюю вершину $$$v_i$$$. Одновременно переместить каждый камень из $$$u_i$$$ на соответствующую ему $$$v_i$$$.

В любой момент каждая вершина может содержать не более одного камня.

Определите, существует ли корректная последовательность операций, которая перемещает камни из начального состояния в целевое.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq n \leq 2000$$$, $$$0\leq m \leq \min(\frac{n(n-1)}{2}, 10^4)$$$) — количество вершин и рёбер в графе.

Вторая строка содержит бинарную строку $$$s$$$, состоящую из '0' и '1'. $$$i$$$-й символ $$$s$$$ обозначает количество камней в $$$i$$$-й вершине в исходном состоянии.

Третья строка содержит бинарную строку $$$t$$$, состоящую из '0' и '1'. $$$i$$$-й символ $$$t$$$ обозначает количество камней в $$$i$$$-й вершине в целевом состоянии.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\leq u, v \leq n$$$) — существует неориентированное ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что граф прост, то есть в графе нет петель и кратных рёбер.

Гарантируется, что количество '1' в $$$s$$$ и $$$t$$$ совпадает.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Для каждого набора входных данных на отдельной строке выведите «Yes» или «No» — существует ли допустимая последовательность операций.

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

Пример
Входные данные
4
2 1
10
01
1 2
11 11
11011001010
01101011100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 1
3 2
110
101
1 2
2 3
3 2
111
111
1 2
2 3
Выходные данные
Yes
Yes
No
Yes