#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 * 1000;
int a[MAXN];
int init_a[MAXN];
int gcd(int a, int b) {
  while (a > 0) {
    b = b % a;
    swap(a, b);
  }
  return b;
}
vector<int> get_prime(int a) {
  vector<int> res;
  for (int i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      res.push_back(i);
      while (a % i == 0) {
        a /= i;
      }
    }
  }
  if (a > 1) {
    res.push_back(a);
  }
  return res;
}
int n;
int process_val(int val, const vector<int>& prime, vector<int>& deleter_cnt,
                vector<int>& deleter, int need_cnt, bool& added) {
  int msk = 0;
  for (int i = 0; i < ((int)(prime.size())); i++) {
    int p = prime[i];
    msk *= 2;
    if (val % p == 0) {
      msk |= 1;
    }
  }
  for (int i = 0; i < ((int)(prime.size())); i++) {
    int p = prime[i];
    if (val % p != 0) {
      if (deleter_cnt[i] < need_cnt) {
        deleter_cnt[i]++;
        if (!added) {
          deleter.push_back(val);
        }
        added = 1;
      }
    }
  }
  return msk;
}
int dp[2][1024][1024];
map<int, int> to_msk_a, to_msk_b;
unsigned int was[1024][1024];
bool dfs(int msk_a, int msk_b, const vector<int>& deleter, int ind,
         multiset<int>& first_group) {
  if (msk_a == 0 && msk_b == 0) {
    return 1;
  }
  if (ind >= ((int)(deleter.size()))) {
    return 0;
  }
  if (was[msk_a][msk_b] < ind) {
    return 0;
  }
  int cur_val = deleter[ind];
  int _msk_a = to_msk_a[cur_val];
  int _msk_b = to_msk_b[cur_val];
  bool was_into = 0;
  if ((msk_a & _msk_a) != msk_a) {
    was_into = 1;
    if (dfs(msk_a & _msk_a, msk_b, deleter, ind + 1, first_group)) {
      first_group.insert(cur_val);
      return 1;
    }
  }
  if ((msk_b & _msk_b) != msk_b || !was_into) {
    if (dfs(msk_a, msk_b & _msk_b, deleter, ind + 1, first_group)) {
      return 1;
    }
  }
  was[msk_a][msk_b] = ind;
  return 0;
}
void _try() {
  memset(was, -1, sizeof was);
  to_msk_a.clear();
  to_msk_b.clear();
  vector<int> prime_a = get_prime(a[0]);
  vector<int> prime_b = get_prime(a[1]);
  assert(((int)(prime_a.size())) <= 10);
  assert(((int)(prime_b.size())) <= 10);
  int need_cnt = ((int)(prime_a.size())) + ((int)(prime_b.size()));
  vector<int> deleter;
  vector<int> deleter_a_cnt(((int)(prime_a.size())));
  vector<int> deleter_b_cnt(((int)(prime_b.size())));
  for (int i = 2; i < n; i++) {
    bool added = 0;
    int msk_a =
        process_val(a[i], prime_a, deleter_a_cnt, deleter, need_cnt, added);
    int msk_b =
        process_val(a[i], prime_b, deleter_b_cnt, deleter, need_cnt, added);
    to_msk_a[a[i]] = msk_a;
    to_msk_b[a[i]] = msk_b;
  }
  memset(dp, 0, sizeof dp);
  dp[0][(1 << ((int)(prime_a.size()))) - 1]
    [(1 << ((int)(prime_b.size()))) - 1] = 1;
  multiset<int> first_group;
  if (dfs((1 << ((int)(prime_a.size()))) - 1,
          (1 << ((int)(prime_b.size()))) - 1, deleter, 0, first_group)) {
    first_group.insert(a[0]);
    cout << "YES\n";
    for (int i = 0; i < n; i++) {
      if (first_group.find(init_a[i]) != first_group.end()) {
        first_group.erase(first_group.find(init_a[i]));
        printf("1 ");
      } else {
        printf("2 ");
      }
    }
    exit(0);
  }
}
int main(int argc, const char* argv[]) {
  cin >> n;
  int _gcd = 0;
  for (int i = 0; i < n; i++) {
    scanf("%i", a + i);
    init_a[i] = a[i];
    _gcd = gcd(_gcd, a[i]);
  }
  if (_gcd != 1) {
    cout << "NO\n";
    return 0;
  }
  random_shuffle(a, a + n);
  for (int i = 1; i < min(n, 5); i++) {
    swap(a[1], a[i]);
    _try();
  }
  cout << "NO\n";
  return 0;
}
