- Модель молекулы
На занятии по химии Наташа сделала очень сложное задание, за которое сразу получила отличную отметку. В задании нужно было собрать пространственную модель молекулы с шариками, обозначающими атомы, и нитями, обозначающими связи. Между некоторыми атомами могло оказаться несколько связей.
Однако набор для построения в лаборатории только один, поэтому сразу по окончании выполнения задания модель нужно разобрать. Хулиган Вова схватил ножницы и уже готов перерезать нити одну за одной (возможно, он уже несколько разрезал), но его остановил вопрос, а сколько же будет получаться не связных кусков после того, как он продолжит разрезать нити.
Вова выписал графовую модель текущего состояния молекулы и занумеровал все нити. Также он готов предоставить вам порядок, в котором он будет разрезать нити. Помогите ему определить, сколько будет получатся не связных кусков молекулы, после каждого его действия.
Обратите внимание, что отдельный атом также считается куском молекулы.
Формат ввода
В первой строке входных данных записаны два целых числа N и M — количество атомов и нитей в модели молекулы (2≤N≤100 000; 1≤M≤100 000). В каждой из следующих M строк через пробел записаны два различных числа Xi и Yi — номера атомов, которые соединяет очередная нить-связь. Атомы занумерованы числами от 1 до N, нити занумерованы числами от 1 до M в порядке перечисления во входных данных.
Далее записано число Q — количество нитей, которое собирается разрезать Вова (1≤Q≤M). В последней строке разделенные пробелами записаны номера этих нитей (числа в этой строке различны).
Формат вывода
Выведите через пробел Q чисел — число кусков молекулы, на которые модель будет распадаться после очердного разреза.