我的思路是，对于一个左边的字符，匹配最右边的未选过的不一样的字符；对于一个右边的字符，匹配最左边的未选过的不一样的字符。剩下没选的如果下标在某一对中间，就插入到这一对中。然而交了之后发现得到的 $k$ 的值并非最大的。

我想知道这种做法为什么假了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,tt,presta,st[N],ed[N],tot;
char s[N];
bool v[N];
vector<int>g[N];
struct tree{
	int data[N*4];
	void add(int p,int l,int r,int x,int k)
	{
		if(l==r)
		{
			data[p]+=k;return;
		}
		int mid=l+r>>1;
		if(x<=mid)add(p<<1,l,mid,x,k);
		else add(p<<1|1,mid+1,r,x,k);
		data[p]=data[p<<1]+data[p<<1|1];
	}
	int askr(int p,int l,int r)
	{
		if(l==r)return l;
		int mid=l+r>>1;
		if(data[p<<1|1])return askr(p<<1|1,mid+1,r);
		else return askr(p<<1,l,mid);
	}
	int askl(int p,int l,int r)
	{
		if(l==r)return l;
		int mid=l+r>>1;
		if(data[p<<1])return askl(p<<1,l,mid);
		else return askl(p<<1|1,mid+1,r);
	}
}t[26];
struct pos{
	int data,lazy;
};
struct tree2{
	pos a[N*4];
	void pushdown(int &p)
	{
		if(!a[p].lazy)return;
		a[p<<1].data=a[p<<1|1].data=a[p].lazy;
		a[p<<1].lazy=a[p<<1|1].lazy=a[p].lazy;
		a[p].lazy=0;
	}
	void add(int p,int l,int r,int L,int R,int k)
	{
		if(L<=l&&r<=R)
		{
			a[p].data=a[p].lazy=k;return;
		}
		pushdown(p);
		int mid=l+r>>1;
		if(L<=mid)add(p<<1,l,mid,L,R,k);
		if(mid<R)add(p<<1|1,mid+1,r,L,R,k);
	}
	int ask(int p,int l,int r,int x)
	{
		if(l==r)return a[p].data;
		pushdown(p);
		int mid=l+r>>1;
		if(x<=mid)return ask(p<<1,l,mid,x);
		else return ask(p<<1|1,mid+1,r,x);
	}
}t2;
int precheck()
{
	int vis[26]={0};
	for(int i=1;i<=n;i++)vis[s[i]-'a']++;
	int ret=0,ret2=0;
	for(int i=0;i<26;i++)
	{
		if(vis[i])++ret;
		if(vis[i]>1)++ret2;
	}
	bool flag=1;
	for(int i=1;i<=n;i++)
		if(s[i]!=s[1])
		{
			flag=0;break;
		}
	if(flag)return 0;
	if(n%2==0)
	{
		if(ret==2&&ret2==1)return -1;
		return 1;
	}
	flag=1;
	for(int i=1;i<=n;i++)
		if(i!=(n+1)/2&&s[i]!=s[1])
		{
			flag=0;break;
		}
	if(flag)return 0;
	if(ret==2&&ret2==1)return -1;
	return 1;
}
int main()
{
	scanf("%d%d",&tt,&tt);
	while(tt--)
	{
		scanf("%d%s",&n,s+1);tot=0;
		presta=precheck();
		if(presta==0)
		{
			puts("Shuiniao");continue;
		}
		if(presta==-1)
		{
			puts("Huoyu");
			puts("1");
			printf("%d ",n);
			for(int i=1;i<=n;i++)printf("%d ",i);
			puts("");continue;
		}
		for(int i=0;i<26;i++)memset(t[i].data,0,sizeof(t[i].data));
		memset(t2.a,0,sizeof(t2.a));
		memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++)
			for(int j=0;j<26;j++)
				if(j!=s[i]-'a')t[j].add(1,1,n,i,1);
		int l=1,r=n,lr=0;
		while(l<r)
		{
			while(l<r&&v[l])l++;
			while(l<r&&v[r])r--;
			if(l>=r)break;
			if(lr==0)
			{
				int ind=t[s[l]-'a'].askr(1,1,n);
				if(ind<=l)break;
				++tot;st[tot]=l;ed[tot]=ind;
				for(int j=0;j<26;j++)
				{
					if(j!=s[l]-'a')t[j].add(1,1,n,l,-1);
					if(j!=s[ind]-'a')t[j].add(1,1,n,ind,-1);
				}
				t2.add(1,1,n,l,ind,tot);
				v[l]=v[ind]=1;
			}
			else
			{
				int ind=t[s[r]-'a'].askl(1,1,n);
				if(ind>=r)break;
				++tot;st[tot]=ind;ed[tot]=r;
				for(int j=0;j<26;j++)
				{
					if(j!=s[r]-'a')t[j].add(1,1,n,r,-1);
					if(j!=s[ind]-'a')t[j].add(1,1,n,ind,-1);
				}
				t2.add(1,1,n,ind,r,tot);
				v[ind]=v[r]=1;
			}
			lr^=1;
		}
		for(int i=1;i<=tot;i++)g[i].clear();
		for(int i=1;i<=n;i++)
			if(!v[i])g[t2.ask(1,1,n,i)].push_back(i);
		printf("Huoyu\n%d\n",tot);
		for(int i=1;i<=tot;i++)
		{
			printf("%d %d ",g[i].size()+2,st[i]);
			sort(g[i].begin(),g[i].end());
			for(int x:g[i])printf("%d ",x);
			printf("%d\n",ed[i]);
		}
	}
	return 0;
}