310. Модель молекулы

Не решаласьСредняя

На занятии по химии Наташа сделала очень сложное задание, за которое сразу получила отличную отметку. В задании нужно было собрать пространственную модель молекулы с шариками, обозначающими атомы, и нитями, обозначающими связи. Между некоторыми атомами могло оказаться несколько связей.

Однако набор для построения в лаборатории только один, поэтому сразу по окончании выполнения задания модель нужно разобрать. Хулиган Вова схватил ножницы и уже готов перерезать нити одну за одной (возможно, он уже несколько разрезал), но его остановил вопрос, а сколько же будет получаться не связных кусков после того, как он продолжит разрезать нити.

Вова выписал графовую модель текущего состояния молекулы и занумеровал все нити. Также он готов предоставить вам порядок, в котором он будет разрезать нити. Помогите ему определить, сколько будет получатся не связных кусков молекулы, после каждого его действия.

Обратите внимание, что отдельный атом также считается куском молекулы.

Формат ввода

В первой строке входных данных записаны два целых числа N N и M M — количество атомов и нитей в модели молекулы ( 2 ≤ N ≤ 100   000 2 \le N \le 100\,000 ; 1 ≤ M ≤ 100   000 1 \le M \le 100\,000 ). В каждой из следующих M M строк через пробел записаны два различных числа X i X_i и Y i Y_i — номера атомов, которые соединяет очередная нить-связь. Атомы занумерованы числами от 1 1 до N N , нити занумерованы числами от 1 1 до M M в порядке перечисления во входных данных.

Далее записано число Q Q — количество нитей, которое собирается разрезать Вова ( 1 ≤ Q ≤ M 1 \le Q \le M ). В последней строке разделенные пробелами записаны номера этих нитей (числа в этой строке различны).

Формат вывода

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

Ограничения

Ограничение времени
2 с
Ограничение памяти
256 МБ

Примеры

Пример 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 

Пример 3

Ввод
2 2
1 2
1 2
2
1 2
Вывод
1 2 

Теги

3.5.1
Нужно войти, чтобы отправить решение.Войти