#include <bits/stdc++.h>
using namespace std;
std ::mt19937 ran(20040924);
int n, a[100000], p, q, fp[9], fq[9], lp, lq, able[100000], List[325], L,
    mask1[325], mask2[325], res[100000];
char dp[325][512][512];
template <typename T>
inline void chkmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
inline void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
inline void read(T &x) {
  T f = 1;
  x = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  x *= f;
}
inline int gcd(int x, int y) {
  int r;
  while (y) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}
inline void factorize(int x, int *f, int &l) {
  l = 0;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) {
      do x /= i;
      while (x % i == 0);
      f[l++] = i;
    }
  if (x > 1) f[l++] = x;
}
inline void enable(int prime) {
  int count = 0;
  for (int i = 0; i < n; ++i)
    if (i != p && i != q && a[i] % prime != 0) {
      able[i] = 1;
      if (count++ == lp + lq) return;
    }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", a + i);
  if (n <= 20) {
    for (int i = 0; i < 1 << n - 1; ++i) {
      int g1 = 0, g2 = 0;
      for (int j = 0; j < n; ++j)
        if (i >> j & 1)
          g1 = gcd(g1, a[j]);
        else
          g2 = gcd(g2, a[j]);
      if (g1 == 1 && g2 == 1) {
        printf("YES\n");
        for (int j = 0; j < n; ++j)
          printf("%d%c", (i >> j & 1) + 1, " \n"[j == n - 1]);
        return 0;
      }
    }
    printf("NO\n");
    return 0;
  }
  for (int T = 10; T--;) {
    p = ran() % n, q = ran() % (n - 1);
    if (q >= p) ++q;
    factorize(a[p], fp, lp);
    factorize(a[q], fq, lq);
    for (int i = 0; i < n; ++i) able[i] = 0;
    for (int i = 0; i < lp; ++i) enable(fp[i]);
    for (int i = 0; i < lq; ++i) enable(fq[i]);
    L = 0;
    for (int i = 0; i < n; ++i)
      if (able[i]) List[++L] = i;
    for (int i = 0; i < 1 << lp; ++i)
      for (int j = 0; j < 1 << lq; ++j) dp[0][i][j] = i == 0 && j == 0;
    for (int i = 1; i <= L; ++i) {
      mask1[i] = 0;
      mask2[i] = 0;
      for (int j = 0; j < lp; ++j)
        if (a[List[i]] % fp[j] == 0) mask1[i] |= 1 << j;
      for (int j = 0; j < lq; ++j)
        if (a[List[i]] % fq[j] == 0) mask2[i] |= 1 << j;
      for (int j = 0; j < 1 << lp; ++j)
        for (int k = 0; k < 1 << lq; ++k) {
          dp[i][j][k] = 0;
          if (dp[i - 1][j & mask1[i]][k])
            dp[i][j][k] = 1;
          else if (dp[i - 1][j][k & mask2[i]])
            dp[i][j][k] = 2;
          else
            dp[i][j][k] = 0;
        }
      if (dp[L][(1 << lp) - 1][(1 << lq) - 1]) {
        printf("YES\n");
        res[p] = 1;
        res[q] = 2;
        for (int i = L, j = (1 << lp) - 1, k = (1 << lq) - 1; i; --i) {
          res[List[i]] = dp[i][j][k];
          if (dp[i][j][k] == 1) j &= mask1[i];
          if (dp[i][j][k] == 2) k &= mask2[i];
        }
        for (int i = 0; i < n; ++i)
          printf("%d%c", res[i] ? res[i] : 1, " \n"[i == n - 1]);
        return 0;
      }
    }
  }
  printf("NO\n");
  return 0;
}
