// Object supporting union (of disjoint sets) and find operations.
class UnionFind
{
	private int count;
	private UnionFind pal;
	
	// (Re)Initialize this object for use by UnionFind.
	public void initializeUnionFind()
	{
		count = 1;
		pal = this;
	}

	// Merge the set associated with this and
	// the set associated with q.
	public void union(UnionFind q)
	{
		UnionFind p = this;
		UnionFind pRoot = p.find();
		UnionFind qRoot = q.find();
		// Merge the smaller set into the larger set.
		if (pRoot.count < qRoot.count)
		{
			pRoot.pal = qRoot;
			qRoot.count = pRoot.count + qRoot.count;
		}
		else
		{
			qRoot.pal = pRoot;
			pRoot.count = pRoot.count + qRoot.count;
		}
	}
	
	// Return the representative of the set associated with this.
	public UnionFind find()
	{
		UnionFind p = this;
		UnionFind prev = p;
		
		// Set p to the last element in the pal list starting at p, 
		// and reverse the pal list.
		while ( p != p.pal ) 
		{	
			UnionFind next = p.pal;
			p.pal = prev;
			prev = p;
			p = next;
		}
		
		// Set the pal of every node in the reversed list to be p.
		while ( prev != prev.pal )
		{
			UnionFind next = prev.pal;
			prev.pal = p;
			prev = next;
		}
		prev.pal = p;
		
		return p;
	}
} // UnionFind