vector<pii> dif;
vector<char> used;


int findP(int a, vector<int> &p, bool fl){
    if (p[a] == a)
        return a;
    int cur = findP(p[a], p, fl);
    if (fl && p[a] != cur)
        if (!used[a]){
            dif.pb(mp(a, p[a]));
            used[a] = 1;
        }
    return p[a] = cur;
}


void mergeSt(int a, int b, vector<int> &p, vector<int> &s, bool fl){
    a = findP(a, p, fl);
    b = findP(b, p, fl);
    if (s[a] > s[b])
        swap(a, b);
    if (fl && p[a] != b)
        if (!used[a]){
            dif.pb(mp(a, p[a]));
            used[a] = 1;
        }
    p[a] = b;
    s[b] += s[a];
}