Через неорганізовану структуру його ферми, фермер Джон вирішив навести лад у стійлах.

У кожній фермі є \(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

Приклад вихідних даних

YES
NO

У першому тестовому випадку можлива наступна послідовність ходів:

Поточне стійло: 1. Ключі на руках: []. Ключі у стійлах: [3, 4, 3, 4, 2]
(взяти ключ кольору 3)
Поточне стійло: 1. Ключі на руках: [3]. Ключі у стійлах: [x, 4, 3, 4, 2]
(переміщення зі стійла 1 до 2 дозволено, тому що у нас ключ кольору C_2=3)
Поточне стійло: 2. Ключі на руках: [3]. Ключі у стійлах: [x, 4, 3, 4, 2]
(взяти ключ кольору 4)
Поточне стійло: 2. Ключі на руках: [3, 4]. Ключі у стійлах: [x, x, 3, 4, 2]
(переміщення зі стійла 2 в 1, потім у 4, потім у 5 дозволено, тому що у нас є ключі кольорів C_4=4 і C_5=3)
Поточне стійло: 5. Ключі на руках: [3, 4]. Ключі у стійлах: [x, x, 3, 4, 2]
(взяти ключ кольору 2 та покласти ключ кольору 3)
Поточне стійло: 5. Ключі на руках: [2, 4]. Ключі у стійлах: [x, x, 3, 4, 3]
(переміщення зі стійла 5 до 4, потім до 1, потім до 3, дозволено, тому що у нас є ключі кольорів C_4=4 і C_3=2)
Поточне стійло: 3. Ключі на руках: [2, 4]. Ключі у стійлах: [x, x, 3, 4, 3]
(взяти ключ кольору 3 та покласти ключ кольору 4)
Поточне стійло: 3. Ключі на руках: [2, 3]. Ключі у стійлах: [x, x, 4, 4, 3]
(перейти зі стійла 3 до стійла 2 і покласти ключ кольору 3)
Поточне стійло: 2. Ключі на руках: [2]. Ключі у стійлах: [x, 3, 4, 4, 3]
(перейти зі стійла 2 до стійла 1 і покласти ключ кольору 2)
Поточне стійло: 1. Ключі на руках: []. Ключі в стійках: [2, 3, 4, 4, 3]

Для другого тесту ФД не може внести ключ кольору \(F_i\) у кожне стійло \(i\) і повернутися у стійло \(1\).

Приклад вхідних даних

5

2 0
1 2
2 2
2 2

2 1
1 1
2 1
2 1
1 2

2 1
1 1
2 1
1 2
1 2

2 1
1 1
1 2
2 1
1 2

5 4
1 2 3 4 4
2 3 5 4 2
5 3 2 4 2
1 2
1 3
1 4
4 5

Приклад вихідних даних

YES
YES
NO
YES
NO

ОЦІНКА:

• Тести 3-6 задовольняють \(N,M\le 8\).
• Тести 7–10 задовольняють \(C_i=F_i\).
• Тести 11–18 не мають додаткових обмежень.