Есть граф из N вершин. Изначально он пустой. Нужно обработать M запросов:
добавить ребро из вершины v1 в вершину v2, при этом вершины v1 и v2 находятся в разных деревьях и вершина v2 является корнем какого-то дерева.
по двум вершинам a и b определить, лежат ли они в одном дереве.
Реализуем СНМ с эвристикой сжатия путей:
Вам же предстоит сделать тест, на котором это решение будет работать долго. Более точно, нужно сделать тест, на котором количество вызовов функции calc_leader
будет не меньше, чем 1/4Mlog2M.
Входной файл содержит два целых числа N и M (1≤N≤106, 1≤M≤105, M≤N).
Выведите M строк. i-ая строка должна иметь вид 1 x y, если i-ый запрос заключается в добавлении ребра из вершины x в вершину y, или 0 x y, если спрашивается, лежат ли вершины x и y в одном дереве.