В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог.

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

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

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

В городе \(n\) автобусных остановок, через которые проходят \(k\) кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, \(i\)-ый маршрут проходит по остановкам \(a_{i, 1}\), \(a_{i, 2}\), …, \(a_{i, l_i}\) (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке \(a_{i,1}\). На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки \(a_{i, l_i}\) автобус оказывается на остановке \(a_{i, 1}\) и едет по маршруту еще раз.

Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План \(j\)-го человека состоит из остановки \(b_j\), на которой человек начнет свое катание и последовательности чисел \(c_{j, 1}\), \(c_{j, 2}\), …, \(c_{j, m_j}\). Эти числа означают следующее: в момент времени 0 человек придет на остановку \(b_j\) и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке \(b_j\), человек сядет в него). На этом автобусе он проедет \(c_{j, 1}\) остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет \(c_{j, 2}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.

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

Петя учится играть в шахматы. Недавно он заметил, что несмотря на то, что кони умеют прыгать через фигуры, они могут мешать друг другу дойти до нужных клеток. Петя поставил на доску двух коней: черного и белого, и для каждого их них выбрал клетку, на которой он хочет его видеть. Теперь ему интересно, какое минимальное число ходов потребуется коням, чтобы дойти до нужных клеток.

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