EduBrick

E. Фишки на графе

1000 мс · 256 МБ · всё или ничего

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

Это ровно та конструкция, ради которой значения Гранди и придумывались.

Формат ввода

В первой строке - числа nn и mm (2≤n≤1052 \le n \le 10^5, 1≤m≤1051 \le m \le 10^5).

В следующих mm строках - рёбра графа. Граф ациклический, кратные рёбра возможны.

В следующей строке - число фишек tt (1≤t≤1051 \le t \le 10^5), затем tt номеров вершин.

Формат вывода

Выведите First, если выигрывает первый игрок, и Second иначе.

Примеры

ввод
3 3
1 2
2 3
1 3
2
1 2
вывод
First
ввод
3 3
1 2
2 3
1 3
2
1 1
вывод
Second
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.