Запити на графі
Після попередніх 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.