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

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

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

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

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