Берляндская компания «Панические технологии» производит определенную стратегически важную продукцию. Единственный завод компании находится в городе $$$1$$$, из которого продукция доставляется во все остальные города на Белых поездах по железнодорожным путям.
Всего в Берляндии $$$N$$$ городов, некоторые из которых соединены ж/д путями. Города (вершины) и ж/д пути (ребра) образуют граф, который по необъяснимому стечению обстоятельств является вершинным кактусом — связным неориентированным графом, в котором каждая вершина лежит не более чем на одном простом цикле. Кроме того, длина всех циклов в этом графе четная.
Каждый поезд движется из города, в котором находится завод, в город назначения по такому маршруту, который позволит посетить минимально возможное количество городов, а если существует несколько таких маршрутов, выбирается случайно один из них. Когда очередной поезд прибывает в пункт назначения, его груз выгружают в бункер, а сам поезд разбирается на месте и больше не используется. Изначально такой алгоритм движения гарантирует, что по каждому ж/д пути поезда будут двигаться в одном направлении, что является необходимым и достаточным условием отсутствия возможности столкновения поездов.
Компания планирует построить еще $$$K$$$ заводов в некоторых городах, из которых продукция будет так же доставляться во все остальные города по тому же алгоритму. Чтобы сохранить гарантию отсутствия возможности столкновения между поездами, компании может потребоваться достроить дополнительные ж/д пути. По законам Берляндии между городами $$$A$$$ и $$$B$$$ разрешено строить новый ж/д путь только в том случае, если непосредственно между ними уже существует ж/д путь. Таким образом, компания решила достроить между некоторыми такими городами парный ж/д путь, предписывая поездам двигаться из $$$A$$$ в $$$B$$$ по одному из путей, а из $$$B$$$ в $$$A$$$ — по другому. В таком случае столкновения между этими городами никогда не произойдет.
Необходимо определить, какое минимальное количество дополнительных законных ж/д путей должна построить компания, чтобы запустить очередной завод и гарантировать, что между поездами не может произойти столкновений.
В первой строке заданы числа $$$N$$$ и $$$M$$$ — количество городов Берляндии и количество существующих ж/д путей ($$$2 \le N \le 10^5$$$, $$$1 \le M \le N-1+N/4$$$).
Следующие $$$M$$$ строк содержат по паре чисел $$$A_i$$$ и $$$B_i$$$ — номера городов, между которыми проложен ж/д путь ($$$1 \le A_i, B_i \le N$$$).
Гарантируется, что граф является вершинным кактусом, не содержит петель и кратных ребер, а все циклы в графе имеют четную длину.
Следующая строка содержит число $$$K$$$ — количество заводов, которое компания планирует построить ($$$1 \le K \le 10^5$$$).
В последней строке перечислены номера городов $$$X_j$$$, в которых будут построены заводы в хронологическом порядке ($$$1 \le X_j \le N$$$).
Выведите $$$K$$$ чисел $$$Y_j$$$ — минимальное количество дополнительных ж/д путей, которые необходимо построить для запуска завода номер $$$j$$$.
7 7 1 2 1 3 3 4 4 7 5 7 3 5 5 6 5 6 2 4 4 5
4 1 2 0 0
На рисунке обозначены города и начальное расположение путей и направлений, по которым проходят поезда из первого примера.
После постройки завода в городе $$$6$$$, необходимо добавить пути между парами городов: $$$\langle 6, 5 \rangle$$$, $$$\langle 5, 3 \rangle$$$, $$$\langle 7, 4 \rangle$$$, $$$\langle 3, 1 \rangle$$$.
После постройки завода в городе $$$2$$$, необходимо добавить пути между парой городов $$$\langle 2, 1 \rangle$$$.
После постройки первого завода в городе $$$4$$$, необходимо добавить пути между парами городов: $$$\langle 4, 3 \rangle$$$, $$$\langle 7, 5 \rangle$$$.
