Петя работает в межгалактическом агентстве путешествий. Он часто получает запросы на поиск пути между двумя планетами по доступным межпланетным дорогам. Петя уже сделал по этому поводу целый ряд наблюдений, и сейчас его интересует следующее. Для каждой планеты \(А\) он хочет знать количество пар планет \(В\) и \(С\), таких что любой путь от планеты \(В\) к планете \(С\) проходит через планету \(А\).

Полицейский гонится за преступником по музею. В начале погони каждый из них находится в одной из \(n\) комнат здания, некоторые комнаты соединены дверями.

Непосредственно перед началом погони в здании сработала сигнализация, и все двери закрылись. Музей использует сверхсовременную систему охраны - каждая дверь принадлежит одному из \(k\) контуров безопасности. Полицейский может с помощью специального пульта управления блокировать и разблокировать все двери некоторого контура. При этом с целью обеспечения безопасности операции он может одновременно разблокировать не более одного контура. Полицейский впервые попал на такое ответственное задание, поэтому очень волнуется. Чтобы случайно не провалить операцию, каждый раз, перейдя из одной комнаты в другую, он блокирует все двери. При этом он очень инициативен и каждую минуту переходит из комнаты в комнату.

Благодаря системе камер, установленной в музее, полицейский в любой момент знает, где находится преступник. Однако поскольку система видеонаблюдения находится в состоянии тестовой эксплуатации, данная информация доступна также во всех комнатах, поэтому преступник тоже знает, где находится полицейский. Преступник наблюдает за всеми перемещениями полицейского. Каждый раз, после того как полицейский переходит из одной комнаты в другую, перед тем, как полицейский заблокирует двери, преступник тоже может перебежать в одну из соседних комнат. Разумеется, он может пробегать только через двери контура, который в настоящее время разблокирован.

Преступник хочет добраться до выхода (который находится в комнате с номером 1), а полицейский - поймать преступника. Если полицейский врывается в комнату, где находится преступник, то преступник не успевает убежать в другую комнату, и полицейский арестовывает его. Если преступник оказывается в комнате с выходом, то он немедленно покидает здание и скрывается в близлежащих районах.

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

Определите, сможет ли полицейский поймать преступника, и если да, то какое минимальное количество перемещений из комнаты в комнату ему для этого потребуется. Если полицейский не сможет поймать преступника, то определите, сможет ли тот убежать, и если да, то сколько переходов из комнаты в комнату ему для этого потребуется.

Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии от классической постановки задачи, где по заданным исходным данным \(D\) требуется решить некоторую оптимизационную задачу \(P\), в обратной задаче по заданной задаче \(P\) и результату вычисления \(R\) требуется подобрать исходные данные \(D\), на которых достигается этот результат. В этой задаче вам предлагается решить обратную задачу к задаче о минимуме на отрезке (range minimum query, RMQ).
Пусть задан массив \(a[1..n]\). Ответ на запрос о минимуме на отрезке \(Q(i, j)\) — это минимальное среди значений \(a[i]\), ..., \(a[j]\). Вам дано \(n\) и последовательность запросов о минимуме на отрезке с ответами. Восстановите исходный массив \(a\).