Ще одна задача про дерева

Є граф із $N$ вершин. Спочатку він порожній. Потрібно обробити $M$ запитів:

• додати ребро з вершини $v_1$ до вершини $v_2$, при цьому вершини $v_1$ і $v_2$ знаходяться в різних деревах і вершина $v_2$ є коренем якогось дерева.

• по двох вершинах $a$ і $b$ визначити, чи лежать вони в одному дереві.

Розв'язання задачі

Реалізуємо СНМ з евристикою стиснення шляхів:

int n, m, l[NMAX];
int calc_leader (int v)
{
     if (l [v]! = v)
         l[v] = calc_leader (l[v]);
     return l [v];
}

int main()
{
     scanf ("%d%d", &n, &m);
     for (int i = 1; i <= n; i ++)
         l[i] = i;
     for (int i = 1; i <= m; i ++)
     {
         int x, y, z;
         scanf ("%d%d%d", &z, &x, &y);
         if (z == 1)
             l[y] = x;
         else
             if (calc_leader (x) == calc_leader (y))
                 printf ("YES\n");
             else
                 printf ("NO\n");
     }
}

Вам же доведеться зробити тест, на якому це рішення працюватиме довго. Більш точно, потрібно зробити тест, на якому кількість викликів функції calc_leader буде не менше ніж $1/4Mlo{g}_{2}M$.

Вхідні дані

Вхідний файл містить два цілих числа $N$ і $M$ ($1\le N\le 10^6$, $1\le M\le 10^5$, $M\le N$).

Вихідні дані

Виведіть $M$ рядків. $i$-ий рядок повинен мати вигляд $1xy$, якщо $i$-ий запит полягає в додаванні ребра з вершини $x$ до вершини $y$, або $0xy$, якщо питається, лежать чи вершини $x$ і $y$ в одному дереві.

Приклади