C. Цивилизация
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Андрей играет в игру «Цивилизация». Дима помогает ему.

В игре «Цивилизация» n городов и m двусторонних дорог. Города пронумерованы целыми числами от 1 до n. Между любой парой городов либо существует единственный путь, либо не существует никакого пути. Путем называется последовательность различных городов v1, v2, ..., vk, в которой между любыми двумя соседними городами vi и vi + 1 (1 ≤ i < k) есть дорога. Длина такого пути равна (k - 1). Давайте говорить, что два города лежат в одной области тогда и только тогда, когда существует путь между этими двумя городами.

В процессе игры происходят события двух типов:

  1. Андрей спрашивает у Димы длину самого длинного пути в области, в которой лежит город x.
  2. Андрей просит Диму объединить область, в которой лежит город x, с областью, в которой лежит город y. Если города лежат в одной области, то объединять области не нужно. Иначе нужно объединить области следующим образом: выбрать город в первой области, город во второй области и связать их дорогой так, чтобы минимизировать длину самого длинного пути в полученной области. Если существует несколько оптимальных способов соединить области, то разрешается выбрать любой.

Диме очень сложно выполнять просьбы Андрея, поэтому он обращается к вам за помощью. Помогите Диме.

Входные данные

В первой строке содержатся три целых числа 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 строк содержит одно из двух событий в следующем формате:

  • 1 xi. Запрос Андрея к Диме на нахождение длины максимального пути в области, содержащей город xi (1 ≤ xi ≤ n).
  • 2 xi yi. Запрос Андрея к Диме на объединение области, содержащей город xi, и области, содержащей город yi (1 ≤ xi, yi ≤ n). Обратите внимание, что xi может быть равно yi.
Выходные данные

Для каждого события первого типа выведите ответ на него в отдельной строке.

Примеры
Входные данные
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1
Выходные данные
4