Задача F. Ещё одна задача про деревья ≡

Условие

Есть граф из N вершин. Изначально он пустой. Нужно обработать M запросов:

1. добавить ребро из вершины v₁ в вершину v₂, при этом вершины v₁ и v₂ находятся в разных деревьях и вершина 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 будет не меньше, чем 14Mlog₂M.

Формат входных данных

Входной файл содержит два целых числа N и M (1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 10⁵, M ≤ N).

Формат выходных данных

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

Ограничения

Примеры тестов

2 2

1 1 2
0 1 2