Problem A

Almost Union-Find

I hope you know the beautiful Union-Find structure. In this problem, you're to implement something similar, but not identical.

The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:

1 p q

Union the sets containing p and q. If p and q are already in the same set, ignore this command.

2 p q

Move p to the set containing q. If p and q are already in the same set, ignore this command

3 p

Return the number of elements and the sum of elements in the set containing p.

Initially, the collection contains n sets: {1}, {2}, {3}, ..., {n}.

Input

There are several test cases. Each test case begins with a line containing two integers n and m (1<=n,m<=100,000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1<=p,q<=n. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each type-3 command, output 2 integers: the number of elements and the sum of elements.

Sample Input

5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3

Output for the Sample Input

3 12
3 7
2 8

Explanation

Initially: {1}, {2}, {3}, {4}, {5}

Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}

Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3})

Collection after operation 1 3 5: {1,2}, {3,4,5}

Collection after operation 2 4 1: {1,2,4}, {3,5}

---

當我們將操作 2 的 p 點抽出時, 賦予它成為新的節點編號, 打個新的映射即可 !


#include <stdio.h>

int p[200001], r[200001], mapped[200001];
long long s[200001];
void init(int n) {
    static int i;
    for(i = 0; i <= n; i++) {
        p[i] = i, s[i] = 0, r[i] = 1;
        mapped[i] = i;
    }
}
int find(int x) {
    return p[x] == x ? x : p[x]=find(p[x]);
}
void joint(int x, int y, int i, int j) {
    if(x == y)
        return;
    s[x] += s[y];
    r[x] += r[y];
    s[y] = 0;
    r[y] = 0;
    p[y] = x;
}
int main() {
    int n, m, op, i, j, t, x, y;
    while(scanf("%d %d", &n, &m) == 2) {
        init(n+m);
        for(i = 0; i <= n; i++)
            s[i] = i;
        while(m--) {
            scanf("%d %d", &op, &i);
            if(op == 3) {
                t = find(mapped[i]);
                printf("%d %lld\n", r[t], s[t]);
            } else if(op == 2) {
                scanf("%d", &j);
                x = find(mapped[i]);
                y = find(mapped[j]);
                if(x != y) {
                    s[x] -= i, r[x]--;
                    mapped[i] = ++n;
                    s[mapped[i]] = i;
                    r[mapped[i]] = 1;
                    joint(find(mapped[i]), find(mapped[j]), i, j);
                }
            } else {
                scanf("%d", &j);
                joint(find(mapped[i]), find(mapped[j]), i, j);
            }
        }
    }
    return 0;
}