「模拟赛」云胡不喜

Description

cc和小xx在玩游戏。有一张nn个点mm条边的图,每个连通块都是一棵有根树,根是连通块内编号最小的点。
两人轮流操作,小cc先手。每次可以选择一个没有被删除的节点xx,把xxxx所有祖先都删除。不能操作的人输。
注意删除点不会影响其余点的父子关系。
cc想知道,假如她和小xx都足够聪明,这个游戏中,先手的SGSG值。
SGSG值:定义mex(S)mex(S)表示不出现在集合S中的最小自然数。考虑一个状态AA,设它的后继状态的SGSG值构成集合FF,那么A的SGSG值就是mex(F)mex(F)

Input

第一行一个整数TT表示数据组数。
对于每组数据,第一行两个整数n,mn,m表示点数和边数。后面mm行描述一条无向边。保证没有重边自环,且一定是森林。

Output

TT行每行一个整数表示答案。

Sample Input

1
2
3
4
5
6
7
8
9
4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2

Sample Output

1
2
3
4
2
2
0
3

HINT

20%20\%的数据:n50n \leq 50
40%40\%的数据:n1000n \leq 1000
100%100\%的数据:n100000,T10n \leq 100000, T \leq 10

Soluiton

40pts

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
#include<bits/stdc++.h>
typedef long long ll;
void setIO() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
}
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

using namespace std;
const int N = 1100;
int head[N], en;
struct Edge {
int u, v, nxt;
}e[N * 2];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int n, m, f[N], g[N];
bool vis[N];
int c[N];
void work(int x, int F, int s) {
++c[s ^ g[x]];
for(int i = head[x]; i;i = e[i].nxt) if(e[i].v != F) work(e[i].v, x, s ^ g[x] ^ f[e[i].v]);
}
void dfs(int x, int F) {
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
g[x] ^= f[y];
}
memset(c,0,sizeof c);
work(x, F, 0);
int i = 0;
while(c[i]) ++i;
f[x] = i;
}

int main() {
setIO();
int T = read();
while(T--) {
n = read(), m = read();
en = 0;
for(int i = 1; i <= n; ++i) vis[i] = g[i] = f[i] = head[i] = 0;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
int ans = 0;
for(int i = 1; i <= n; ++i) if(!vis[i]) {
dfs(i, 0);
ans ^= f[i];
}
writeln(ans);
}
return 0;
}

100pts

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
typedef long long ll;
void setIO() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
}
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

using namespace std;
const int N = 110000;
int head[N], en;
struct Edge {
int u, v, nxt;
}e[N * 2];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int n, m, f[N], g[N];
bool vis[N];
int rt[N];
int tag[N * 32];
struct T {
int l, r, s;
}t[N * 32];
int tot;
void down(int x, int k) {
if(!tag[x]) return;
tag[t[x].l] ^= tag[x];
tag[t[x].r] ^= tag[x];
if((tag[x] >> k) & 1)
swap(t[x].l, t[x].r);
tag[x] = 0;
}
int merge(int x, int y, int k) {
if(!x || !y) return x | y;
if(k == -1)
return x;
down(x, k);
down(y, k);

t[x].l = merge(t[x].l, t[y].l, k - 1);
t[x].r = merge(t[x].r, t[y].r, k - 1);
t[x].s = t[t[x].l].s + t[t[x].r].s; //下面会错,不能直接siz相加,要用已经合并过的
// t[x].s = t[x].s + t[y].s;
return x;
}
void ins(int &o, int x, int k) {
if(!o) {
o = ++tot;
t[o].l = t[o].r = t[o].s = 0;
tag[o] = 0;
}
if(k == -1) {
t[o].s = 1;
return;
}
down(o, k);
if(!(x & (1 << k))) ins(t[o].l, x, k - 1);
else ins(t[o].r,x, k - 1);
t[o].s = t[t[o].l].s +t[t[o].r].s;
}
bool fg;
int query(int x) {
int p = x, res = 0;
for(int i = 16;~i; --i) {
down(p, i);
if(t[t[p].l].s == (1 << i)) res |= (1 << i), p = t[p].r;
else p = t[p].l;
}
return res;
}
void dfs(int x, int F) {
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
g[x] ^= f[y];
}
for(int i = head[x]; i; i= e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
tag[rt[y]] ^= g[x] ^ f[y];
rt[x] = merge(rt[x], rt[y], 16);
}
ins(rt[x], g[x],16);
f[x] = query(rt[x]);
}

int main() {
setIO();
int T = read();
while(T--) {
n = read(), m = read();
tot = en = 0;
for(int i = 1; i <= n; ++i) rt[i] = vis[i] = g[i] = f[i] = head[i] = 0;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
int ans = 0;
for(int i = 1; i <= n; ++i) if(!vis[i]) {
dfs(i, 0);
ans ^= f[i];
}
writeln(ans);
}
return 0;
}