mergingcommunities.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class UnionFind {
    private int[] parent;
    private int[] size;
    public  UnionFind(int n){
        this.parent = new int[n+1];
        this.size = new int[n+1];
        for(int i=1;i<n+1;i++){
            parent[i] = i;
            size[i] = 1;
        }
    }
    public int findParent(int root){
        if(root == parent[root]){
            return root;
        }
        return findParent(parent[root]);
    }
    
    public void unionData(int p,int q){
        p = findParent(p);
        q = findParent(q);
        if(p == q) return;
        if(size[p] > size[q]){
            parent[q] = p; 
            size[p] += size[q];
        }
        else{
            parent[p] = q;
            size[q] += size[p];
        }
    }
    public int calculateSize(int p){
        int parentData = findParent(p);
        return size[parentData];
    }
    
}
public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        UnionFind uf = new UnionFind(n);
        int m = sc.nextInt();
        for(int i =0;i<m;i++){
            String cmd = sc.next();
            if (cmd.equals("Q")){
                int val = sc.nextInt();
                //System.out.println(val);
                System.out.println(uf.calculateSize(val));
                
            }
            else if(cmd.equals("M")){
                int p = sc.nextInt();
                int q= sc.nextInt();
                uf.unionData(p,q);
                
            }
        }
    }
}