ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Нынче в моде кактусы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Бесспорно, екатеринбургские трамваи — лучшие в мире. Тем не менее, крупнейшей трамвайной сетью в России обладает Санкт-Петербург. Ещё совсем недавно Санкт-Петербургская трамвайная система была включена в книгу рекордов Гиннесса как самая большая в мире.
Два завсегдатая трамвайного форума из Екатеринбурга решили съездить в Санкт-Петербург на празднование столетнего юбилея пуска трамвая в этом городе. От своих питерских друзей гости узнали, что в течение последних 15 лет объёмы трамвайного движения постоянно сокращаются, на многих магистралях трамвайные пути демонтированы. Так, в центре города трамвайное движение сведено к минимуму, а пассажирская сеть разделена на 3 фрагмента, так что из любой части Санкт-Петербурга уже нельзя добраться в любую другую на трамвае.
Problem illustration
А ещё екатеринбуржцы узнали, что в Санкт-Петербурге теперь в моде кактусы. По возвращении в Екатеринбург они решили посадить в своём рабочем кабинете кактус. Кактус — это связный неориентированный граф, каждое ребро которого лежит не более чем на одном простом цикле. Одна вершина кактуса соприкасается с землёй и называется корнем кактуса.
Но вскоре выяснилось, что кактусы стали слишком популярны и уже растут дома у всех заядлых посетителей трамвайного форума. Тогда друзья решили избавиться от кактуса весьма оригинальным способом. Они по очереди выбирают некоторое ребро кактуса и разрубают его. При этом оно удаляется, и если кактус разбивается на две части, то та часть, которая больше не связана с корнем, выбрасывается.
Друзья договорились, что тот, кто отрубит последнее растущее от корня ребро, получит трамвайный проездной на следующий месяц. Определите, кто из них выиграет при оптимальной стратегии обоих.

Исходные данные

Вместе с модой на кактусы екатеринбуржцы следуют питерской моде описывать множество рёбер кактуса в виде совокупности рёберно-непересекающихся путей. В первой строке даны целые положительные числа n, m и r, где n — количество вершин кактуса, m — количество путей, r — номер корневой вершины кактуса, 1 ≤ rn ≤ 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 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1610. Нынче в моде кактусы