Есть граф из $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$ в одном дереве.