D. Carousel
题意：
n个数字围成一个环，现在要求对n个数进行染色。
染色要求是，对于相邻的两个数，如果不同的话，要求颜色也要不一样。那么如果相邻两个数相同，颜色可以不同，也可以相同。
思路：
一、如果所有数字都一样的话，只需要染上同一种颜色即可。
二、如果数字的个数有偶数个，那么只需要两种颜色，按照1 2 1 2...1 2 1 2这样染色即可。
三、如果数字的个数有奇数个，去看遍历一下这个环，看是不是有相邻的数字是一样的，如果有，我们只需要对其中一组相邻的数字染上同一种颜色，对于剩下的继续按照1 2 1 2...1 2 1 2染色即可。其实这样等价是把奇数个数字变成了意义上的偶数个。(注意这是个环，第一个数字和最后一个数字也是相邻的 需要特判下)
如果不存在相邻的相同数字的话，则需要三种颜色，按照1 2 1 2...1 2 1 2染色，最后一个数字染色为2。

#include<bits/stdc++.h>
using namespace std;
int a[1<<18];
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        set<int> s;
        for(int i=1;i<=n;i++) cin>>a[i],s.insert(a[i]);
        if(s.size()==1){
            cout<<1<<endl;
            while(n--) cout<<"1 ";
        }
        else if(n%2==0)
        {
            cout<<2<<endl;
            for(int i=1;i<=n/2;i++) cout<<"1 2 ";
        }
        else
        {   
            int flag=0;
            for(int i=1;i<=n;i++) 
                if(a[i]==a[i-1]) {
                    flag=1;break;
                }
            if(a[n]==a[1]) flag=1;
            if(flag){
                cout<<2<<endl;
                flag=0;
                int k=1;
                for(int i=1;i<=n;i++){
                    if(!flag && a[i]==a[i-1]){
                        k^=3;
                        flag=1;
                    }
                    cout<<k<<" ";
                    k^=3;
                }
            }
            else {
                cout<<3<<endl;
                for(int i=1;i<=n/2;i++) cout<<"1 2 ";
                cout<<3;
            }
        }
        cout<<endl;
    }
    return 0;
}