Республиканская олимпиада по информатике, 2011 год, 10-11 классы

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

В городе есть $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$ строках задаются запросы. Подаются запросы двух видов:
$+$ $x$ $y$ — кандитат $x$ изменил мнение улицы $y$, и теперь улица $y$ агитируют за него $(1 \le x \le 2, 1 \le y \le M).$
$q$ $x$ $y$ $k$ — Выведите сколько улиц агитирует за кандидата $k$ между перекрестками $x$ и $y$ $(1 \le k \le 2).$ Изначально все улицы агитируют за кандидата 1.

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

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

Примеры:

Вход

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

Ответ

2
1