int findComponent(int u)
{
	int p = parent[u];
	assert(p <= N && p >= 1);
	if(p == u)
	{
		assert(comp[p] == 0);
		return p;
	}

	int head = findComponent(p);
	comp[u] = comp[u] ^ comp[p];
	return parent[u] = head;
}

void merge(int u, int v)
{
	int uc = findComponent(u);
	int vc = findComponent(v);

	assert(parent[u] == uc && parent[v] == vc);
	parent[vc] = uc;
	assert(comp[vc] == 0);
	comp[vc] = comp[v] ^ 1 ^ comp[u];
}