Быстрые ответы
Быстрые ответы
Джо любит компьютерные игры. Сейчас он должен решить головоломку. Перед ним лежит огромная карта с укрепленными городами. Враг Джо - очень сильный и хитрый персонаж, который умеет соединять и разъединять города своими командами. Два города называются связанными, если они соединены либо непосредственно, либо через некоторое множество других связанных между собой городов в некоторый момент времени. Когда город отключается, он становится изолированным от других, то есть удаляется вся история его соединений; история соединений между другими городами не изменяется. Каждое соединение является двунаправленным. Изначально все города изолированы. Джо необходимо быстро отвечать, связаны ли два города, в соответствии с историей команд персонажа.
Напишите программу, которая на основе входных данных подсчитает количество ответов "да" и количество ответов "нет" на вопросы следующего вида: связаны ли между собой города towni
и townj
?
Входные данные
Состоит из нескольких тестов, каждый из которых представляет собой отдельную карту городов и команд персонажа:
1) Количество городов на карте n (n ≤ 10000);
2) Набор команд вида:
a) ctowni townj
, где towni
и townj
- целые числа от 1 до no_of_towns. Команда означает, что towni
и townj
соединяются.
b) dtowni
, где towni
- целое число от 1 до no_of_towns. Команда означает, что towni
отсоединяется.
c) qtowni townj
, где towni
и townj
- целые числа от 1 до no_of_towns. Команда означает запрос: соединены ли towni
с townj
?
d) e, завершающая список команд.
Каждая команда расположена в отдельной строке. Команды (a), (b), (c) могут идти в любом порядке. Связность городов изменяется при поступлении команд типа (a) и (b). Каждая команда типа (c) обрабатывается в соответствии с текущей конфигурацией.
Выходные данные
Вывести найденные два числа в одной строке в виде: n1
, n2
, как показано в примере.
Пример
Приведенный пример соответствует карте из 4 укрепленных городов. Персонаж дает 9 команд. Имеется в точности n1
ответов yes и n2
ответов no.
4 c 1 2 c 3 4 q 1 3 c 2 3 q 1 4 d 2 q 4 1 q 2 4 e
2 , 2