Запросы на графах
После предыдущих 2 задач вы заметили, что наш герой увлекается задачами на запросы. Он предлагает вам новую задачу, которая напоминает задачу о кратчайшем пути в динамическом графе.
Вам даны N узлов. В каждом запросе вы либо добавляете ребро между 2 узлами (двунаправленное ребро), либо вычисляете расстояние между 2 узлами. Предположим, что граф всегда остаётся без петель и циклов.
1) Добавить ребро между 2 узлами, длина которого равна 1. Этот запрос записывается как “1 i j”.
2) Вывести расстояние между i-м и j-м узлом. Если пути между этими узлами нет, вывести -1. Этот запрос записывается как “2 i j”.
Входные данные
Дано целое число N (1 ≤ N ≤ 100000) — количество узлов, и Q (1 ≤ Q ≤ 100000) — количество запросов. Следующие Q строк содержат по одному запросу каждого из указанных выше типов.
Выходные данные
Для каждого запроса типа “2 i j” выведите расстояние между i-м и j-м узлом. Если пути между этими узлами нет, выведите -1.