1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STRL 2048
#define MAXN 200005
#define RL() fgets(temp, MAX_STRL, stdin)
#define WL(X) fputs( (X) , stdout)

int par[MAXN], rank[MAXN];
int N, M;

void init(void) {
    int i=((N+1)<<1); // Same gang(N) + Different gang(N) (N*2)
    while(i--) {
        par[i]=i;
        rank[i]=1;
    }
}

int find(int u) { return par[u]==u?u:(par[u]=find(par[u])); }
char same(int u, int v) { return find(u)==find(v)?1:0; }
void uni(int u, int v) {
    int x = find(u);
    int y = find(v);
    if (x==y) return;
    if (rank[x]<rank[y]) {
        par[x] = y;
    } else {
        if (rank[x]==rank[y])
            ++rank[x];
        par[y] = x;
    }
}

int main(void) {
    char temp[MAX_STRL];
    int T;
    RL();
    T = atoi(temp);
    while (T-->0) {
        RL();
        sscanf(temp, "%d %d", &N, &M);
        init();
        int i=0;
        for (i=0; i<M; ++i) {
            RL();
            int u, v;
            char op;
            sscanf(temp, "%1c %d %d", &op, &u, &v);
            switch (op) {
                case 'D':
                    uni(u,v+N); uni(u+N, v); // assign to different gangs
                    break;
                default:
                    if (same(u,v)||same(u+N,v+N))  // test if same
                        WL ( "In the same gang.\n" );
                    else if (same(u,v+N)||same(u+N,v)) // test if different
                        WL ( "In different gangs.\n" );
                    else
                        WL ( "Not sure yet.\n" ); // undetermined
                    break;
            }
        }
    }
    return 0;
}