C. Разящий удар звездного десанта
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После долгих лет войны с арахнидами человечество нашло возможность нанести разящий удар. Последние удачи военной разведки указали на логово королевы арахнидов, и вот вы уже на планете насекомоподобных со своим отрядом перед разрытыми норами, ведущими в сложную систему вражеских тоннелей и залов. Ситуация усугубляется тем, что у вас нет никакого плана этой системы. Однако вы знаете, что таких залов не больше $$$10^5$$$ и королева находится в зале с номером $$$9999$$$.

Вы находитесь в зале номер 0 и снаряжаете несколько дронов, которых запускаете во все входы, к которым имеете доступ. Дроны должны исследовать всю систему и дать вам возможность спланировать ваш удар. Каждый дрон время от времени выходит с вами на связь и передает информацию о переходах между залами. Несмотря на то, что человеческая мысль позволила сделать дроны невидимыми для арахнидов, глубина залегания пещер такова, что какая-то часть данных теряется в помехах. Поэтому дроны передают информацию весьма фрагментарно.

Как только вы обнаруживаете, что дроны передали достаточно данных о том, чтобы построить маршрут между вами и залом, в котором находится королева, вы должны дать сигнал к атаке.

Если вдруг вы пропустите момент, когда маршрут может быть построен, а вы не отдали команду об атаке, вы сразу же попадаете под трибунал как пособник арахнидов.

Спланируйте успешную атаку и не попадите под трибунал.

Протокол взаимодействия

Для чтения данных программа должна использовать стандартный ввод и осуществлять печать на стандартный вывод.

В начале работы программы в первой строке подается число $$$N$$$ ($$$0 \lt N \lt 10^5-1$$$), которое задает, что в начале вы имеете доступ к входам в залы $$$0, 1, 2,\ldots, N$$$.

Далее ваша программа будет получать со стандартного ввода данные от дронов. Каждая порция данных располагается в отдельной строке.

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

Первым передается целое число $$$K$$$ ($$$1\leqslant K\leqslant 42$$$), которое задает количество переходов. После него через пробел идут пары чисел $$$0\leqslant f_i, t_i \lt 10^5$$$, которые задают, что дронами был обнаружен переход между залами с номерами $$$f_i$$$ и $$$t_i$$$.

После получения каждой порции данных вам надо выдать «WAIT», если вы не видите пути от вашего местоположения к королеве, и тогда дроны продолжат свою работу, либо «ATTACK», если вы можете построить такой путь и надо атаковать. Указанные команды выводятся в отдельной строке на стандартный вывод. После вывода команды «ATTACK» ваша программа должна завершить свою работу.

Примеры
Входные данные
4
2 4 6 11 12
~
5 9 10 8 10 1 2 2 7 3 9
~
1 9999 7
~
Выходные данные
~
~
WAIT
~
WAIT
~
ATTACK
Входные данные
1
3 3 4 9999 4 2 3
~
1 1 2
~
Выходные данные
~
~
WAIT
~
ATTACK
Примечание

Эта задача немного необычна — в ней вам предстоит реализовать интерактивное взаимодействие с тестирующей системой. Это означает, что вы можете делать запросы и получать ответы в online-режиме. Обратите внимание, что ввод/вывод в этой задаче — стандартный (то есть с экрана на экран). После вывода очередного запроса обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию fflush(stdout), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.

При работе программы знак $$$\sim$$$ выводить не нужно.