B. Система навигации
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карта Бертауна может быть представлена как набор из $$$n$$$ перекрестков, пронумерованных от $$$1$$$ до $$$n$$$ и соединенных между собой $$$m$$$ односторонними дорогами. Гарантируется, что возможно добраться от любого перекрестка до любого другого, путешествуя по существующим дорогам. Длина какого-либо пути от одного перекрестка до другого равна количеству переходов по дорогам в этом пути. Кратчайшим путем от перекрестка $$$v$$$ до другого перекрестка $$$u$$$ называется путь, который начинается в $$$v$$$, заканчивается в $$$u$$$ и имеет минимальную длину среди всех таких путей.

Поликарп живет около перекрестка $$$s$$$ и работает в здании неподалеку от перекрестка $$$t$$$. Каждый день он ездит от $$$s$$$ до $$$t$$$ на машине. Сегодня он выбрал следующий путь до своей работы: $$$p_1$$$, $$$p_2$$$, ..., $$$p_k$$$, где $$$p_1 = s$$$, $$$p_k = t$$$, а все другие элементы этой последовательности являются промежуточными перекрестками, перечисленными в том порядке, в котором Поликарп их посещал. Поликарп никогда не посещал один и тот же перекресток дважды, таким образом, все элементы этой последовательности попарно различны. Заметьте, что вы знаете путь Поликарпа заранее (он фиксирован), и он не обязательно является одним из кратчайших путей от $$$s$$$ до $$$t$$$.

Машина Поликарпа оснащена сложной навигационной системой. Опишем, как она работает. Когда Поликарп начинает свою поездку с перекрестка $$$s$$$, система выбирает какой-либо кратчайший путь от $$$s$$$ до $$$t$$$ и показывает его Поликарпу. Пусть следующий перекресток в выбранном пути равен $$$v$$$. Если Поликарп выбирает ехать дорогой от $$$s$$$ до $$$v$$$, то навигатор показывает ему тот же самый кратчайший путь (очевидно, он будет стартовать с $$$v$$$ с того момента, как Поликарп доедет до этого перекрестка). Однако если Поликарп выбирает доехать до другого перекрестка $$$w$$$, навигатор перестраивает путь: как только Поликарп доезжает до $$$w$$$, навигационная система выбирает какой-то кратчайший путь от $$$w$$$ до $$$t$$$ и показывает его Поликарпу. Тот же самый процесс продолжается до тех пор, пока Поликарп не доедет до $$$t$$$: если Поликарп едет по дороге, рекомендованной системой, то она оставляет кратчайший путь, который уже был построен; но если Поликарп выбирает какой-либо другой путь, система перестраивает путь по тем же самым правилам.

Рассмотрим пример. Пусть карта Бертауна выглядит следующим образом, а Поликарп едет путем $$$[1, 2, 3, 4]$$$ ($$$s = 1$$$, $$$t = 4$$$):

Ознакомьтесь с картинкой по ссылке http://tk.codeforces.com/a.png

  1. Когда Поликарп начинает свой путь у перекрестка $$$1$$$, система выбирает какой-то кратчайший путь от $$$1$$$ до $$$4$$$. Существует только один такой путь, он равен $$$[1, 5, 4]$$$;
  2. Поликарп выбирает поехать к перекрестку $$$2$$$, который не лежит на кратчайшем пути, выбранным системой. Когда Поликарп доезжает до $$$2$$$, навигатор перестраивает путь, выбирая какой-то кратчайший путь от $$$2$$$ до $$$4$$$, например, $$$[2, 6, 4]$$$ (заметьте, что он может выбрать $$$[2, 3, 4]$$$);
  3. Поликарп выбирает поехать к перекрестку $$$3$$$, который не лежит на кратчайшем пути, выбранным системой. Когда Поликарп доезжает до $$$3$$$, навигатор перестраивает путь, выбирая единственный кратчайший путь от $$$3$$$ до $$$4$$$, который равен $$$[3, 4]$$$;
  4. Поликарп доезжает до $$$4$$$ по дороге, выбранной навигатором, таким образом, система больше ничего не перестраивает.

В этом сценарии случилось $$$2$$$ перестроения маршрута. Заметьте, что если система выберет $$$[2, 3, 4]$$$ вместо $$$[2, 6, 4]$$$ в течение второго шага, то будет только $$$1$$$ перестроение (так как Поликарп едет по этому же пути, система сохранит путь $$$[3, 4]$$$ в течение третьего шага).

Пример показывает, что количество перестроений может различаться даже несмотря на то, что карта Бертауна и путь, выбранный Поликарпом, никогда не меняются. Имея эту информацию (карту и путь Поликарпа), сможете ли вы определить минимальное и максимальное количество перестроений маршрута, которые могли произойти в течение поездки?

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le m \le 2 \cdot 10^5$$$) — количество перекрестков и односторонних дорог в Бертауне соответственно.

Далее следуют $$$m$$$ строк, каждая из которых описывает дорогу. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), обозначающих дорогу от перекрестка $$$u$$$ к перекрестку $$$v$$$. Все дороги в Бертауне попарно различны, и это значит, что каждая упорядоченная пара $$$(u, v)$$$ встречается не более одного раза среди этих $$$m$$$ строк (но если существует дорога $$$(u, v)$$$, то дорога $$$(v, u)$$$ также может существовать).

Следующая строка содержит одно целое число $$$k$$$ ($$$2 \le k \le n$$$) — количество перекрестков в пути Поликарпа от его дома до его работы.

Последняя строка содержит $$$k$$$ целых чисел $$$p_1$$$, $$$p_2$$$, ..., $$$p_k$$$ ($$$1 \le p_i \le n$$$, все эти целые числа попарно различны) — перекрестки в пути Поликарпа в том порядке, в котором он их посещал. $$$p_1$$$ равно перекрестку, около которого живет Поликарп ($$$s = p_1$$$), а $$$p_k$$$ равно перекрестку, около которого Поликарп работает ($$$t = p_k$$$). Гарантируется, что для каждого $$$i \in [1, k - 1]$$$ существует дорога от $$$p_i$$$ до $$$p_{i + 1}$$$, таким образом, путь идет по дорогам Бертауна.

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

Выведите два числа: минимальное и максимальное количество перестроений маршрута, которые могут произойти в течение поездки.

Примеры
Входные данные
6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4
Выходные данные
1 2
Входные данные
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
7
1 2 3 4 5 6 7
Выходные данные
0 0
Входные данные
8 13
8 7
8 6
7 5
7 4
6 5
6 4
5 3
5 2
4 3
4 2
3 1
2 1
1 8
5
8 7 5 2 1
Выходные данные
0 3