Ликантропия

Это интерактивная задача.

Джейкоб --- оборотень, умеющий превращаться в волка. Сейчас он в теле человека и хочет превратиться в волка. Но его волчьей сущности надоели частые превращения туда-обратно и она пытается сопротивляться превращению.

Для превращения в волка, мозг Джейкоба посылает сигнал в нервную систему. Сигнал распространяется по нервной системе вниз, от мозга к сердцу. Нервная система Джейкоба состоит из $n$ нейронов и $m$ синапсов. Мозг генерирует сигнал в первом нейроне, после чего начинается его распространение до сердца (нейрона с номером $n$). Каждый синапс может передавать сигнал из $a_i$-го нейрона в $b_i$-й ($a_i < b_i$). После того, как сигнал приходит в нейрон, он должен отправиться дальше по какому-нибудь синапсу. Если синапса, по которому сигналу можно отправиться, нет, сигнал затухает и превращения в волка не происходит. Если сигнал доходит до сердца, начинается превращение в волка.

Волчья сущность хочет помешать Джейкобу начать превращение в волка. Для этого она, каждый раз, сразу после того, как сигнал приходит в нейрон, может временно дестабилизировать работу не более, чем $k$ синапсов, и они не смогут переносить сигнал, пока он не уйдёт из того нейрона, в котором он находится в данный момент. После ухода сигнала, волчья сущность снова сможет дестабилизировать (возможно, другие) синапсы, и так далее, до затухания сигнала, либо до начала превращения в волка. Работоспособность ранее дестабилизированных синапсов при этом восстанавливается.

Помогите волчьей сущности провалить попытку превращения.

Для корректной работы программы после каждой операции вывода данных вам необходимо делать следующие операции:

• В языке Pascal: flush(output);
• В C/C++: fflush(stdout);
• В Java: System.out.flush();
• В Python: sys.stdout.flush();

Кроме этого, не забывайте после каждой выведенной строки ставить перевод строки.