Республиканская олимпиада по информатике 2011 года за 11 класс | Казахстанские олимпиады

Задача F. Выборы

В городе есть $N$ перекрестков и $M$ улиц. С любого прекрестка можно доехать до любого другого и этот путь единственный. В городе началась борьба за выборы в мэры города. В финальную часть выборов вышли два кандидата. Агитация проходит на улицах. На каждой улице есть люди которые агитируют за конкретного кандидата.

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ и $M$ $(1 \le N,M \le 10^5).$ В каждой из следующих $M$ строках задаются описание улицы $a$ и $b$ — перекрестки, которые соединеняет это улица $(1 \le a, b \le N).$ В следующей строке задается $K$ — количество запросов $(1 \le K \le 10^5).$ В следующих $K$ строках задаются запросы. Подаются запросы двух видов:

Формат выходного файла

Для каждого запроса второго типа (описанного вверху) выведите ответ.

Примеры

Вход

3 2
1 2
1 3
3
q 1 3 1
+ 2 1
q 1 3 1

Выход

2
1