ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

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

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
4 4
1 2
2 3
1 3
3 4
3
2 4 3
1 2 3
3 1
1 2
1
1
3
Автор задачи: Дмитрий Полетаев (подготовка — Алексей Самсонов)
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2008