405380: GYM101931 C Налево пойдешь...

C. Налево пойдешь...ограничение по времени на тест1.5 секундограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

Помогите хоббитам выбрать тот лабиринт, который приведет их к цели. Известно, что такой лабиринт только один, остальные ведут в тупик.

Входные данные

На вход подается число $$$1<N\leq 300$$$ - количество входов в лабиринты, перед которыми стоят путники.

Далее следуют $$$N$$$ описаний этих лабиринтов. В первой строке описания задается число $$$2<K\leq 1000$$$ и $$$M$$$ - соответственно количество залов в лабиринте и количество описаний переходов. После этого следуют $$$M$$$ пар чисел $$$(a_i, b_i)$$$, $$$0\leq a_i, b_i<K$$$, которые задают, что из зала $$$a_i$$$ есть переход в зал $$$b_i$$$ и обратно. Описания переходов не повторяются.

Ворота перед хоббитами ведут всегда в зал номер $$$0$$$. Известно, что из зала с номером $$$K-1$$$ есть выход на ту сторону Мглистых гор.

Выходные данные

Одно число, которое соответствует номеру лабиринта, который возможно пройти от зала номер $$$0$$$ до зала номер $$$K-1$$$. Лабиринты нумеруются начиная с единицы.

ПримерыВходные данные

2
3 2
0 1
1 2
4 1
0 1

Выходные данные

1

Входные данные

3
5 3
2 0
1 3
3 4
4 2
0 1
2 3
4 3
0 2
1 3
2 3

Выходные данные

3

Входные данные

2
4 2
1 0
2 3
5 1
0 4

Выходные данные

2

Входные данные

2
10 3
0 2
1 3
4 9
8 5
0 5
2 4
6 3
0 3
6 7

Выходные данные

2

Входные данные

2
5 4
0 3
0 1
0 2
1 3
4 4
0 1
0 2
1 2
1 3

Выходные данные

2