Є граф із вершин. Спочатку він порожній. Потрібно обробити запитів:
додати ребро з вершини до вершини , при цьому вершини і знаходяться в різних деревах і вершина є коренем якогось дерева.
по двох вершинах і визначити, чи лежать вони в одному дереві.
Реалізуємо СНМ з евристикою стиснення шляхів:
Вам же доведеться зробити тест, на якому це рішення працюватиме довго. Більш точно, потрібно зробити тест, на якому кількість викликів функції calc_leader
буде не менше ніж .
Вхідний файл містить два цілих числа і (, , ).
Виведіть рядків. -ий рядок повинен мати вигляд , якщо -ий запит полягає в додаванні ребра з вершини до вершини , або , якщо питається, лежать чи вершини і в одному дереві.