Карта Бертауна может быть представлена как набор из $$$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$$$):

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]$$$ в течение третьего шага).

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