#include <iostream>
using namespace std;

class UnionFind
{
public : 
	int* a;
	int n;
	
	UnionFind( int sz )
	{
		n = sz;
		a = new int[n+1];
		for (int i=1 ; i<=n ; i++) a[i] = -1;
	}
	
	// + Weighted Union
	void Union( int p , int q )
	{
		int rp = Find(p);
		int rq = Find(q);
		if (rp == rq) return;
		
		int sp = -a[rp] , sq = -a[rq];
		if (sp < sq)
		{
			a[rp] = rq;
			a[rq] = -(sp+sq);
		}
		else
		{
			a[rq] = rp;
			a[rp] = -(sp + sq);
		}
	}
	
	// + Collapsing Find
	int Find( int p )
	{
		int r = p;
		while ( a[r] >= 0 ) r = a[r];
		
		int c;
		while ( a[p] >= 0 ) 
		{
			c = a[p];
			a[p] = r;
			p = c;
		}
		
		return r;
	}
	
	bool isInSameSet( int p , int q )
	{
		int rp = Find(p);
		int rq = Find(q);
		return rp == rq;
	}
};

int main()
{
	UnionFind u(9);
	
	cout<<u.isInSameSet(1 , 3)<<"\n";
	u.Union( 1 , 3 );
	u.Union( 2 , 4 );
	u.Union( 3 , 4 );
	for (int i=1 ; i<=9 ; i++) cout<<u.a[i]<<" ";
	cout<<u.isInSameSet( 1 , 3)<<"\n";
	cout<<u.isInSameSet( 2 , 3)<<"\n";
	cout<<u.isInSameSet( 4 , 3)<<"\n";
	cout<<u.isInSameSet( 1 , 2)<<"\n";
	cout<<u.isInSameSet( 1 , 5)<<"\n";
	
	for (int i=1 ; i<=9 ; i++) cout<<u.a[i]<<" ";
	
	return 0;
}