import java.util.Scanner;

public class DSmove {
    private Node[] nodes;

    public DSmove(int n) {
        this.nodes = new Node[n];

        for (int i=0; i < n; i++) {
            nodes[i] = new Node(i);
        }
    }

    public Node find(int x) {
        Node node = nodes[x];
        while (node.id != node.parent.id)
            node = node.parent;
        return node;
    }

    public void union(int p, int q) {
        Node rootP = find(p);
        Node rootQ = find(q);

        if (rootP.id == rootQ.id) return;

        if (rootP.size > rootQ.size) {
            //Move rootQ to be a child of rootP

            //Start by increasing the size of the immediateChildren array (if necessary)
            if (rootP.numberOfImmediateChildren == rootP.immediateChildren.length) {
                increaseArraySize(n);
            }

            //Add rootQ as an immediate child of rootP
            rootP.immediateChildren[rootP.numberOfImmediateChildren] = rootQ;
            //Increate the number of immediate children that rootP has
            rootP.numberOfImmediateChildren++;
            //Increase the total size of rootP
            rootP.size += rootQ.size;

            //Mark rootQ as largest child of rootP if that is indeed the case
            if (rootQ.size > rootP.largestChild.size) {
                rootP.largestChild = rootQ;
            }
        } else {
            //DIY
        }
    }

    private void increaseArraySize(Node n) {
        //Do the smart size increase (check your books)
        Node[] newArray = new Node[n.immediateChildren.length * 2];

        for (int i = 0; i < n.numberOfImmediateChildren; i++) {
            newArray[i] = n.immediateChildren[i];
        }

        n.immediateChildren = newArray;
    }

    private class Node {
        private int id;
        private int size;
        private int numberOfImmediateChildren;

        private Node parent = this;
        private Node[] immediateChildren = new Node[1];
        private Node largestChild = null;

        Node(int i) {
            this.id = i;
            this.size = 1;
            this.numberOfImmediateChildren = 0;
        }
    }
}