思路

分类讨论。

1. 若只有一种动物，则只需要一种颜色。
2. 若动物种数大于等于二，则至少需要两种颜色。原因是，若存在两种以上动物，则至少存在一对相邻动物种类不同，否则就只有一种动物。此时，为这两个动物染色就需要两种颜色。
   1. 若动物个数为偶数，则只需要两种颜色。原因是，$1212 \cdots 12$ 就能保证所有相邻动物颜色不同。
   2. 若动物个数为奇数。
      1. 若可以找到一对相邻动物，它们的种类相同，则只需两种颜色。原因是，从这对相邻动物中间将序列分成两段，必有一段长度为奇数，另一段长度为偶数，不妨设左奇右偶，则左边可以用 $1212 \cdots 1$ 保证所有相邻动物颜色不同，右边可以用 $1212 \cdots 12$ 保证相邻动物颜色不同。由于左边的首与右边的尾也不同，因此所有相邻动物颜色都不同。
      2. 若所有相邻动物种类都不同，则需要三种颜色。原因是，如果只用两种颜色，为了使所有相邻位置的颜色全部不同，染色方案只能是 $1212 \cdots 1$ 或 $2121 \cdots 2$，无论如何都会发现最后一个位置和第一个位置颜色相同。为了使它们的颜色不同，至少需要增加一种颜色，且只要将第一个位置改成 $3$ 就能保证所有相邻位置颜色不同。

时间复杂度 $O(n)$。

#include <iostream>

#define endl "\n"

using namespace std;

constexpr int N = 200010;

int t[N], c[N];

void solve() {
  int n;
  cin >> n;

  for (int i = 0; i < n; i++) cin >> t[i];
  t[n] = t[0];

  bool one_type = true;
  for (int i = 1; i <= n; i++)
    if (t[i] != t[i - 1]) {
        one_type = false;
        break;
    }

  int k;
  if (one_type) {
    k = 1;
    for (int i = 0; i < n; i++) c[i] = 1;
  } else if (n % 2 == 0) {
    k = 2;
    c[0] = 1;
    for (int i = 1; i < n; i++) c[i] = c[i - 1] ^ 3;
  } else {
    int cut = -1;
    for (int i = 1; i <= n; i++)
      if (t[i] == t[i - 1]) {
        cut = i - 1;
        break;
      }

    if (~cut) {
      k = 2;
      c[cut] = c[cut + 1] = 1;
      for (int i = cut - 1; ~i; i--)    c[i] = c[i + 1] ^ 3;
      for (int i = cut + 2; i < n; i++) c[i] = c[i - 1] ^ 3;
    } else {
      k = 3;
      c[0] = 1;
      for (int i = 1; i < n; i++) c[i] = c[i - 1] ^ 3;
      c[0] = 3;
    }
  }

  cout << k << endl;
  for (int i = 0; i < n; i++) cout << c[i] << " ";
  cout << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}