EduBrick

E. Фишки на графе: ход

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

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

Формат ввода

В первой строке - числа 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 номеров вершин.

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

Если выигрывает второй игрок, выведите Second.

Иначе выведите First, а во второй строке - номер фишки (в порядке ввода) и номер вершины, куда её передвинуть. Из нескольких ходов выведите лексикографически наименьший.

Примеры

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