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