Паутина Ананси
(Время: 2 сек. Память: 64 Мб Сложность: 60%)
Усатый-Полосатый XIII решил отомстить Ананси за освобождение бабочек, разрушив дом Ананси – его паутину. Паутина состоит из N узлов, некоторые из которых соединены нитями. Будем говорить, что два узла принадлежат одному кусочку, если от одного узла до другого можно добраться по нитям паутины.
Усатый-Полосатый уже решил, какие нити и в каком порядке он будет рвать, и теперь хочет узнать, на сколько кусочков будет распадаться паутина после каждого из его действий.
Входные данные
В первой строке входного файла INPUT.TXT через пробел записаны числа N и M – количество узлов и нитей в паутине (2 ≤ N ≤ 105; 1 ≤ M ≤ 105). В каждой из следующих M строк через пробел записаны два различных числа – номера узлов, которые соединяет очередная нить. Узлы занумерованы числами от 1 до N, нити занумерованы числами от 1 до M в том порядке, в котором они перечислены. Далее записано число Q – количество нитей, которое собирается порвать Усатый-Полосатый (1 ≤ Q ≤ M). В последней строке записаны номера этих нитей – различные числа, отделяемые друг от друга пробелом.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать Q чисел через пробел – число кусочков, из которых будет состоять паутина Ананси после каждого обрыва нити.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 4
1 2
2 3
1 3
3 4
3
2 4 3 | 1 2 3 |
| 2 | 3 1
1 2
1
1 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
