Codeforces Round 260 (Div. 1) |
---|
Закончено |
Андрей играет в игру «Цивилизация». Дима помогает ему.
В игре «Цивилизация» n городов и m двусторонних дорог. Города пронумерованы целыми числами от 1 до n. Между любой парой городов либо существует единственный путь, либо не существует никакого пути. Путем называется последовательность различных городов v1, v2, ..., vk, в которой между любыми двумя соседними городами vi и vi + 1 (1 ≤ i < k) есть дорога. Длина такого пути равна (k - 1). Давайте говорить, что два города лежат в одной области тогда и только тогда, когда существует путь между этими двумя городами.
В процессе игры происходят события двух типов:
Диме очень сложно выполнять просьбы Андрея, поэтому он обращается к вам за помощью. Помогите Диме.
В первой строке содержатся три целых числа n, m, q (1 ≤ n ≤ 3·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — количество городов, количество уже имеющихся дорог и количество событий соответственно.
Каждая из следующих m строк содержит два целых числа ai и bi (ai ≠ bi; 1 ≤ ai, bi ≤ n). Эти числа обозначают дорогу между городами ai и bi. Между двумя городами не может быть более одной дороги.
Каждая из следующих q строк содержит одно из двух событий в следующем формате:
Для каждого события первого типа выведите ответ на него в отдельной строке.
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1
4
Название |
---|