Запити на графі#7248
Після попередніх задач ви помітили, що наш герой захоплюється задачами на запити. Він пропонує вам нову задачу, яка нагадує задачу про найкоротший шлях у динамічному графі.
Вам дано вузлів. У кожному запиті ви можете додати ребро між вузлами (двонаправлене ребро) або обчислити відстань між вузлами. Припустимо, що граф ніколи не містить петель і циклів.
1) Додати ребро між вузлами, причому довжина цього ребра дорівнює . Цей запит представлений як "1 i j".
2) Вивести відстань між -м і -м вузлом. Якщо між цими вузлами немає шляху, вивести . Цей запит представлений як "2 i j".
Вам дано ціле число (1 \leq N \leq 100000) - кількість вузлів, і (1 \leq Q \leq 100000) - кількість запитів. Наступні рядків містять по одному запиту кожен, однієї з вищезазначених форм.
Для кожного запиту типу "2 i j" виведіть відстань між -м і -м вузлом. Якщо між цими вузлами немає шляху, виведіть .
Приклад 1