eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Паутина Ананси

Паутина Ананси

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Усатый-Полосатый XIII решил отомстить Ананси за освобождение бабочек, разрушив дом Ананси — его паутину. Паутина состоит из N узлов, некоторые из которых соединены нитями. Будем говорить, что два узла принадлежат одному кусочку, если от одного узла до другого можно добраться по нитям паутины.

Усатый-Полосатый уже решил, какие нити и в каком порядке он будет рвать, и теперь хочет узнать, на сколько кусочков будет распадаться паутина после каждого из его действий.

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

В первой строке через пробел записаны числа N и M — количество узлов и нитей в паутине (2N100000, 1M100000). В каждой из следующих M строк через пробел записаны два различных числа — номера узлов, которые соединяет очередная нить. Узлы занумерованы числами от 1 до N, нити занумерованы числами от 1 до M в том порядке, в котором они перечислены. Далее записано число Q — количество нитей, которое собирается порвать Усатый-Полосатый (1QM). В последней строке записаны номера этих нитей — различные числа, отделяемые друг от друга пробелом.

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

Выведите через пробел Q чисел — число кусочков, из которых будет состоять паутина Ананси после каждого обрыва нити.

Пример

Входные данные #1
4 4
1 2
2 3
1 3
3 4
3
2 4 3
Выходные данные #1
1 2 3 
Автор Д.Полетаев, А.Самсонов
Источник Ural SU Contest. Petrozavodsk Summer Session, August 2008