Из-за неорганизованной структуры его амбара, фермер Джон решил навести порядок в стойлах.
В каждом амбаре есть \(N\) стойл, помеченных от \(1\) до \(N\) (\(1 \le N \le 10^5\)) и \(M\).
(\(0 \le M \le 10^5\)) двунаправленных коридоров, соединяющих пары стойл друг с другом. \(i\)-ое стойло окрашено в цвет \(C_i\) и изначально имеет
единственный ключ цвета \(S_i\) в нем. ФД придется переносить ключи, чтобы успокоить
коров и навести порядок в стойлах.
ФД начинает игру в стойле \(1\), не держа никаких ключей, и ему разрешено несколько раз сделать один из следующих ходов:
- Взять ключ в стойле, в котором он сейчас находится. ФД может держать несколько ключей одновременно. раз.
- Положить ключ, который он держит, в стойло, в котором он сейчас находится. В стойле может находиться несколько ключей одновременно.
- Войти в стойло \(1\), начав движение.
- Войти в стойло, отличное от стойла \(1\), перемещаясь по коридору. Он может сделать это только в том случае, если он в настоящее время держит ключ, который
того же цвета, что и стойло, в которое он входит.
К сожалению, кажется, что ключи находятся не на своих местах. Чтобы восстановить порядок в амбаре \(i\)-ое стойло требует, чтобы в нём находился
один ключ и он имел цвет \(F_i\). Гарантируется, что \(S\) является перестановкой \(F\).
Для \(T\) разных амбаров (\(1\le T\le 100\)) ФД стартует в стойле \(1\) и должен
поместить каждый ключ в соответствующее место и вернуься обратно в стойло \(1\). Для
каждого из \(T\) амбаров, пожалуйста, ответьте, возможно ли это сделать.
ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):
Первая строка содержит
\(T\), количество амбаров (подтестов).
Каждому подтесту будет предшествовать пустая строка. Затем первая строка
каждого набора входных данных содержит два целых числа \(N\) и \(M\).
Вторая строка каждого теста содержит \(N\) целых чисел. \(i\)-е число в этой строке, \(C_i\), означает, что стойло \(i\) имеет цвет \(C_i\) (\(1 \le C_i \le N\)).
Третья строка каждого теста содержит \(N\) целых чисел. \(i\)-е число в этой строке, \(S_i\), означает, что стойло \(i\) изначально содержит ключ цвета \(S_i\)
(\(1 \le S_i \le N\)).
Четвертая строка каждого теста содержит \(N\) целых чисел. \(i\)-е число в
этой строка, \(F_i\), означает, что в стойле \(i\) должен быть ключ цвета \(F_i\).
(\(1 \le F_i \le N\)).
Далее следуют \(M\) строк каждого теста. \(i\)-я из этих строк содержит
два различных целых числа, \(u_i\) и \(v_i\) (\(1 \le u_i, v_i \le N\)). Это представляет
что между стойлами \(u_i\) и \(v_i\) существует коридор. Нет повторяющихся коридоров.
Сумма \(N\) по всем амбарам не будет превышать \(10^5\), а сумма \(M\) по
все амбарам не будет превышать \(2\cdot 10^5\).
ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):
Для каждого амбара выведите YES в новой строке, если ФД может положить
ключ цвета \(F_i\) к каждому стойлу \(i\) и вернуться обратно в стойло \(1\). В противном случае,
вывести NO в новой строке.
ОБРАЗЕЦ ВВОДА:
2
5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5
4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5
4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3
|
YES
NO
|