carousel.cpp

/* 

Author: Mike Mirzayanov

Link: https://codeforces.com/blog/entry/75246

The answer to this problem is at most 3. Let's prove it by construction.

Firstly, if all ti are equal then the answer is 1. Otherwise, there are at least two different values 
in the array 𝑡 so the answer is at least 2. If 𝑛 is even then the answer is always 2 because you can 
color figures in the following way: [1,2,1,2,…,1,2]. If 𝑛 is odd then consider two cases. The first 
case is when some pair of adjacent figures have the same type. Then the answer is 2 because you can 
merge these two values into one and get the case of even 𝑛. Otherwise, all pairs of adjacent figures have 
different types and if you consider this cyclic array as a graph (cycle of length 𝑛) then you can notice 
that it isn't bipartite so you need at least 3 colors to achieve the answer (color all vertices in such a 
way that any two adjacent vertices have different colors). And the answer looks like [1,2,1,2,…,1,2,3].

*/

#include <bits/stdc++.h>

using namespace std;

int solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	if (count(a.begin(), a.end(), a[0]) == n) {
		cout << 1 << endl;
		for (int i = 0; i < n; ++i) {
			cout << 1 << " ";
		}
		cout << endl;
		return 0;
	}
	
	if (n % 2 == 0) {
		cout << 2 << endl;
		for (int i = 0; i < n; ++i) {
			cout << i % 2 + 1 << " ";
		}
		cout << endl;
		return 0;
	}
	
	for (int i = 0; i < n; ++i) {
		if (a[i] == a[(i + 1) % n]) {
			vector<int> ans(n);
			for (int j = 0, pos = i + 1; pos < n; ++pos, j ^= 1) {
				ans[pos] = j + 1;
			}
			for (int j = 0, pos = i; pos >= 0; --pos, j ^= 1) {
				ans[pos] = j + 1;
			}
			cout << 2 << endl;
			for (int pos = 0; pos < n; ++pos) {
				cout << ans[pos] << " ";
			}
			cout << endl;
			return 0;
		}
	}
	
	cout << 3 << endl;
	for (int i = 0; i < n - 1; ++i) {
		cout << i % 2 + 1 << " ";
	}
	cout << 3 << endl;
    return 0;    
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int q;
cin >> q;
for (int qq = 0; qq < q; qq++) {
    solve();
}

	return 0;
}