Збереження#4137
Найвідоміша картина в Байтлендії — портрет дами з комп'ютерною мишею Леонардо да Бітчі — потребує збереження. Робота буде проводитися в двох вузькоспеціалізованих лабораторіях. Процес збереження розділено на кілька етапів, і для кожного з них відомо, в якій лабораторії він відбудеться.
Перевезення дуже цінної та крихкої картини створює додатковий ризик, тому його слід уникати, коли це можливо. Ідеально було б, якби вся робота в першій лабораторії була виконана, а потім картину було переміщено до другої. На жаль, існує кілька залежностей між етапами збереження — деякі з них потрібно завершити, перш ніж інші можуть початися. Ваше завдання — знайти порядок етапів збереження, який мінімізує кількість разів, коли картину потрібно переміщати з однієї лабораторії в іншу. Збереження може початися в будь-якій з двох лабораторій.
Перша строка вхідних даних містить кількість тестових випадків . Опис тестових випадків слідує:
Перша строка кожного тестового випадку містить два цілі числа, розділені пробілом та (1 \le n \le 100000, 0 \le m \le 1000000) — кількість етапів збереження та кількість залежностей між ними. У наступній строці знаходяться цілих чисел, розділених пробілом — -те з них дорівнює , якщо -й етап збереження відбудеться в першій лабораторії, і в іншому випадку. Наступні строк містять пари цілих чисел , (1 \le i, j \le n), що позначають, що -й етап має бути завершено перед тим, як -й може початися.
Ви можете припустити, що завжди можливо впорядкувати етапи збереження так, щоб усі залежності були задоволені.
Виведіть відповіді на тестові випадки в порядку, в якому вони з'являються у вхідних даних. Для кожного тестового випадку виведіть одну строку, що містить мінімальну кількість разів, коли картину потрібно транспортувати між лабораторіями.
Приклад 1