给第一次打 USACO 的我带来了一点小小的震撼。

先考虑无解的情况：$N$ 为奇数是无解的充要条件。

• 充分性证明：根据定义，平方串的长度显然是偶数，因此每次从原字符串中删除的字符数量也一定是偶数。当 $N$ 为奇数时，原串长度 $3N$ 也是奇数，每次从中删去偶数数量的字符一定删不完。
• 必要性证明：当 $N$ 为偶数时，原串中一定有 $N$ 个 C，$N$ 个 O 和 $N$ 个 W。因此，一定有一种合法的删法是：依次从原串中删除这 $N$ 个 C、O 和 W。

由以上必要性证明中给出的方法可知，若有解，则操作次数 $M$ 一定不大于 $3$。

那么，我们只需要对这三种做法分别讨论即可。

$M=1$ 的做法很显然，只需要判断一下原串是否是平方串即可。
$M=3$ 的做法已在无解的必要性证明中给出，即依次删除字母 C、O 和 W。
关键在于 $M=2$ 的做法。

我们发现，题目中还有一个条件是我们目前还没有用到过的：原串是由若干个 COW、OWC 和 WCO 拼接而成的。这三个字符串有一个至关重要的性质：三个字符串中任意两个字符串之间的最长公共子串的长度为 $2$。

• 对于 COW 和 OWC，它们的最长公共子串为 OW。
• 对于 COW 和 WCO，它们的最长公共子串为 CO。
• 对于 OWC 和 WCO，它们的最长公共子串为 WC。

利用这个性质，就可以想出 $M=2$ 的做法：

0. 当 $M=2$ 时，我们要做的就是把原串划为两个不相交的子序列，使这两个子序列均为平方串。
1. 将 $N$ 个长度为 $3$ 的字符段序列从中间分为两个字符段序列（即前 $\frac{N}{2}$ 个字符段为一组，后 $\frac{N}{2}$ 个字符段为一组），分别记为 $A$ 和 $B$。
2. 依次比较 $A$ 和 $B$ 中位置相同的两个字符段。根据上面提到的性质，这两个字符段的最长公共子串长度一定为 $2$。因此，我们把这个子串提取出来放进一个平方串，剩下那个字母放进另一个平方串。
3. 这样处理完 $A$ 和 $B$ 后，我们得到了两组字符。这两组字符一定是原串的子序列，且一定是平方串。

可能听起来比较抽象，让我们举个例子。以第三组样例 COWCOWOWCOWCOWCOWC 为例：

1. 将其从中间分开，分为 $A=$ COWCOWOWC 和 $B=$ OWCOWCOWC 两个组。
2. 比较 $A$ 中第一个组 COW 和 $B$ 中第一个组 OWC，其最长公共子串为 OW，因此将 OW 放进第一个平方串，将 C 放进另一个平方串。
3. 比较 $A$ 中第二个组 COW 和 $B$ 中第二个组 OWC，其最长公共子串为 OW，因此将 OW 放进第一个平方串，将 C 放进另一个平方串。
4. 比较 $A$ 中第三个组 OWC 和 $B$ 中第三个组 OWC，其最长公共子串为 OWC，但是这里为了便于理解，我们仍然选择将它们的子串 OW 放进第一个平方串，将 C 放进另一个平方串。
5. 最终我们得到的两个平方串分别是 OWOWOWOWOWOW 和 CCCCCC，它们显然都是 COWCOWOWCOWCOWCOWC 的子序列。

任意一个满足题目要求且有解的字符串，都一定可以通过这样的方法被划分为两个平方串。因此，$M$ 一定小于等于 $2$。

于是这道非常巧妙的构造题就做完了。附上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+5;
int Case,n,k,a[MAXN];
string s;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cin.tie(0);
    cin>>Case>>k;
    while(Case--){
        cin>>n>>s;
        s=' '+s;
        if(n&1){
            cout<<-1<<'\n';
            continue;
        }
        bool c=1;
        for(int i=1;i<=n*3/2;i++){
            if(s[i]!=s[i+n*3/2])c=0;
        }
        if(c){
            cout<<1<<'\n';
            for(int i=1;i<=n*3;i++)cout<<"1 ";
            cout<<'\n';
            continue;
        }
        for(int i=1;i<=n/2;i++){
            int l=(i-1)*3+1,r=(i+n/2-1)*3+1;
            if(s[l]==s[r])a[l]=a[l+1]=a[r]=a[r+1]=1,a[l+2]=a[r+2]=2;
            if(s[l]==s[r+1])a[l]=a[l+1]=a[r+1]=a[r+2]=1,a[l+2]=a[r]=2;
            if(s[l]==s[r+2])a[l+1]=a[l+2]=a[r]=a[r+1]=1,a[l]=a[r+2]=2;
        }
        cout<<2<<'\n';
        for(int i=1;i<=n*3;i++)cout<<a[i]<<" ";
        cout<<'\n';
    }
}