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

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

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

  1. добавить ребро из вершины v1 в вершину v2, при этом вершины v1 и v2 находятся в разных деревьях и вершина v2 является корнем какого-то дерева.
  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 $\lt$= n; i ++)
		l[i] = i;
	for (int i = 1; i $\lt$= 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 будет не меньше, чем 14Mlog2M.

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

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

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

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

Ограничения

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

Стандартный вход Стандартный выход
1
2 2
1 1 2
0 1 2

0.086s 0.015s 13