(mathcal{Decription})
Link.
定义一棵圣诞树：
-
是仙人掌。
-
不存在两个同一环上的点，度数均 (ge 3)。
给出 (n) 棵互不相关的圣诞树，双人博弈，每轮切断一棵圣诞树的一条边，并且与该树根不向连的部分全部消失，不能操作者负。求先手是否有必胜策略。
多测，(T,nle 100)，(mle 500)。
(mathcal{Solution})
没有什么不说人话的定理和结论，这里只应用 SG 函数和 Nim 游戏的基础知识。
本题解中，定义树上“长度”为两点间边的数量。
首先，考虑从根连出多条链的图，显然是 Nim 游戏，每堆石子就是链的长度，根的 SG 函数为这些长度的异或和。
接下来考虑任意一棵树，发现上述结论可以归纳地推广。根据定义，全局 SG 函数为各部分独立 SG 函数异或和，得到：
注意这里 (operatorname{sg} (u)) 实际上表示 (u) 子树的 SG 函数值。其中 (+1) 意为每堆石子（链）的长度都 (+1)。
回忆一下 SG 函数的定义：
此后，考虑从 ((*)) 式的角度求环的 SG 函数。环的后继状态为删除环上任意一条边得到两条链，而链是 Nim 游戏，SG 函数为链长异或和，可以解决。形式地，设环 (C) 的大小为 (n)，有：
分 (n) 的奇偶性讨论：
-
(2|n Rightarrow 2 ot|(n-1))，而 (a+b=n-1)，所以 (a,b) 奇偶性不同，则它们二进制最低位不同。那么两数异或值不可能为 (0)，即集合中不存在 (0)，那么此时 (operatorname{sg} (C)=0)。
-
(2 ot|n Rightarrow 2|(n-1))，而 (a+b=n-1)，同理地，两数异或值必然为偶数，而且显然存在 (0)。得到 (operatorname{sg} (C)=1)。
综上，(operatorname{sg} (C)=[2 ot|n])。
回到本题，“圣诞树”的定义保证了环在缩点后的图中是叶子，所以对于环，用环的 SG 函数算，否则用树的 SG 函数算，最后求每棵圣诞树的 SG 异或就能判断先手胜负啦。
单棵树复杂度 (mathcal O(n))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
const int MAXN = 100, MAXM = 500;
int n, m, ecnt, head[MAXN + 5], dep[MAXN + 5], sg[MAXN + 5];
bool vis[MAXN + 5];
struct Edge { int to, nxt; } graph[MAXM * 2 + 5];
inline void link ( const int s, const int t ) {
graph[++ ecnt] = { t, head[s] };
head[s] = ecnt;
}
inline int calcSG ( const int u, const int fe ) {
/*
返回值表示当前找到的环的顶点（唯一可能度数 >= 3 的点），若不在环上，返回 0。
*/
vis[u] = true;
for ( int i = head[u], v, cir; i; i = graph[i].nxt ) {
if ( ( i ^ 1 ) == fe || !( v = graph[i].to ) ) continue;
if ( vis[v] ) {
sg[v] ^= ( dep[u] - dep[v] + 1 ) & 1;
graph[i ^ 1].to = 0;
return v;
}
dep[v] = dep[u] + 1, cir = calcSG ( v, i );
if ( !cir ) sg[u] ^= sg[v] + 1;
else if ( cir ^ u ) return cir;
}
return 0;
}
inline void clear () {
ecnt = 1;
for ( int i = 1; i <= n; ++ i ) head[i] = sg[i] = dep[i] = vis[i] = 0;
}
int main () {
for ( int T; ~scanf ( "%d", &T ); ) {
int ans = 0;
while ( T -- ) {
clear ();
scanf ( "%d %d", &n, &m );
for ( int i = 1, u, v; i <= m; ++ i ) {
scanf ( "%d %d", &u, &v );
link ( u, v ), link ( v, u );
}
calcSG ( 1, 0 ), ans ^= sg[1];
}
puts ( ans ? "Sally" : "Harry" );
}
return 0;
}