Є граф із $N$ вершин. Спочатку він порожній. Потрібно обробити $M$ запитів: \begin{itemize} \item додати ребро з вершини $v_1$ до вершини $v_2$, при цьому вершини $v_1$ і $v_2$ знаходяться в різних деревах і вершина $v_2$ є коренем якогось дерева. \item по двох вершинах $a$ і $b$ визначити, чи лежать вони в одному дереві. \end{itemize} \subsection{Розв'язання задачі} Реалізуємо \textbf{СНМ} з евристикою стиснення шляхів: \begin{lstlisting}[language=C++] 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"); } } \end{lstlisting} Вам же доведеться зробити тест, на якому це рішення працюватиме довго. Більш точно, потрібно зробити тест, на якому кількість викликів функції \texttt{calc_leader} буде не менше ніж $1/4 M log_2 M$. \InputFile Вхідний файл містить два цілих числа $N$ і $M$ ($1 ≤ N ≤ 10^6$, $1 ≤ M ≤ 10^5$, $M ≤ N$). \OutputFile Виведіть $M$ рядків. $i$-ий рядок повинен мати вигляд $1\ x\ y$, якщо $i$-ий запит полягає в додаванні ребра з вершини $x$ до вершини $y$, або $0\ x\ y$, якщо питається, лежать чи вершини $x$ і $y$ в одному дереві.