Бесспорно, екатеринбургские трамваи — лучшие в мире. Тем не менее, крупнейшей трамвайной сетью
в России обладает Санкт-Петербург. Ещё совсем недавно Санкт-Петербургская трамвайная система была
включена в книгу рекордов Гиннесса как самая большая в мире.
Два завсегдатая трамвайного форума из Екатеринбурга решили съездить в Санкт-Петербург на празднование
столетнего юбилея пуска трамвая в этом городе.
От своих питерских друзей гости узнали, что в течение последних 15 лет объёмы трамвайного движения
постоянно сокращаются, на многих магистралях трамвайные пути демонтированы. Так, в центре города
трамвайное движение сведено к минимуму, а пассажирская сеть разделена на 3 фрагмента, так что
из любой части Санкт-Петербурга уже нельзя добраться в любую другую на трамвае.
А ещё екатеринбуржцы узнали, что в Санкт-Петербурге теперь в моде кактусы. По возвращении
в Екатеринбург они решили посадить в своём рабочем кабинете кактус. Кактус — это связный
неориентированный граф, каждое ребро которого лежит не более чем на одном простом цикле.
Одна вершина кактуса соприкасается с землёй и называется корнем кактуса.
Но вскоре выяснилось, что кактусы стали слишком популярны и уже растут дома у всех
заядлых посетителей трамвайного форума. Тогда друзья решили избавиться от кактуса
весьма оригинальным способом. Они по очереди выбирают некоторое ребро кактуса и разрубают его.
При этом оно удаляется, и если кактус разбивается на две части, то та часть,
которая больше не связана с корнем, выбрасывается.
Друзья договорились, что тот, кто отрубит последнее растущее от
корня ребро, получит трамвайный проездной на следующий месяц.
Определите, кто из них выиграет при оптимальной стратегии обоих.
Исходные данные
Вместе с модой на кактусы екатеринбуржцы следуют питерской моде описывать
множество рёбер кактуса в виде совокупности рёберно-непересекающихся путей.
В первой строке даны целые положительные числа n, m и r, где
n — количество вершин кактуса, m — количество путей, r — номер
корневой вершины кактуса, 1 ≤ r ≤ n ≤ 50000.
Каждая из следующих m строк содержит путь в виде списка вершин.
Путь начинается с числа ni — длины списка, 2 ≤ ni ≤ 100000.
Далее в строке следует ni целых чисел — номера вершин пути
в порядке обхода. Смежные вершины любого пути различны. Между каждой парой вершин может лежать
только одно ребро; каждое ребро кактуса может встречаться во входных данных только один раз.
Результат
Выведите «First», если при правильной игре проездной выиграет тот,
кто сделает первый ход. В противном случае выведите «Second».
Примеры
исходные данные | результат |
---|
17 2 1
15 3 4 5 6 7 8 3 2 9 10 11 12 13 14 9
6 2 1 15 16 17 15
| First
|
16 2 1
15 3 4 5 6 7 8 3 2 9 10 11 12 13 14 9
5 2 1 15 16 1
| Second
|
Автор задачи: Александр Ипатов, Владимир Яковлев
Источник задачи: XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.