#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")

const ll inf = 1'000'000'000;


#ifdef lisie_bimbi
namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
std::vector<int> C;
std::vector<int> X, Y;
std::vector<std::vector<int>> adj;

void quit(const char* message) {
    printf("%s\n", message);
    exit(0);
}

int count_components(const std::vector<int>& S) {
  int components_cnt = 0;
  std::vector<bool> vis(N, false);
  for (int i = 0; i < N; i++) {
      if (vis[i])
          continue;
      components_cnt++;

      std::queue<int> q;
      vis[i] = true;
      q.push(i);
      while (!q.empty()) {
          int cur = q.front();
          q.pop();
          for (int nxt : adj[cur])
              if (!vis[nxt] && S[nxt] == S[cur]) {
                  vis[nxt] = true;
                  q.push(nxt);
              }
      }
  }
  return components_cnt;
}

} // namespace

int perform_experiment(std::vector<int> E) {
    calls_cnt++;
    if (calls_cnt > CALLS_CNT_LIMIT)
        quit("Too many calls");
    if ((int)E.size() != N)
        quit("Invalid argument");
    for (int i = 0; i < N; i++)
        if (!(-1 <= E[i] && E[i] <= N))
            quit("Invalid argument");

    std::vector<int> S(N);
    for (int i = 0; i < N; i++)
        S[i] = (E[i] == -1 ? C[i] : E[i]);

    return count_components(S);
}
#endif


vector<vector<int>> v;
vector<int> used;

void dfs(int u){
    used[u] = 1;
    for(auto i : v[u]){
        if(!used[i]){
            dfs(i);
        }
    }
}

int n;
vector<int> c;

int get(int u){
    vector<int> e(n, n);
    e[u] = -1;
    used.clear();
    used.resize(n);
    used[v[u][0]] = 1;
    used[u] = 1;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            cnt++;
            dfs(i);
        }
    }
    for(int i = 0; i < n; i++){
        e[v[u][0]] = i;
        int x = perform_experiment(e);
        if(x == cnt + 1){
            return i;
            break;
        }
    }
}

vector<vector<int>> d;

void solve(int l, int r, int col){
    if(l + 1 == r){
        c[l] = col;
        return;
    }
    int m = (l + r) / 2;
    vector<int> e(n, n);
    for(int i = l; i < m; i++){
        e[i] = -1;
    }
    if(d[l][m] == -1){
        d[l][m] = perform_experiment(e);
    }
    e[0] = col;
    int x = perform_experiment(e);
    //cout << "aaaaaaaaa " << l << " " << r << " " << col << "      " << m << endl;
    //cout << x << " " << d[l][m] << endl;
    if(x == d[l][m]){
        solve(l, m, col);
    }
    e.clear();
    e.resize(n, n);
    for(int i = m; i < r; i++){
        e[i] = -1;
    }
    if(d[m][r] == -1){
        d[m][r] = perform_experiment(e);
    }
    e[0] = col;
    x = perform_experiment(e);
    //cout << "bbbbbbbbbbbbbb " << l << " " << r << " " << col << "      " << m << endl;
    //cout << x << " " << d[m][r] << endl;
    if(x == d[m][r]){
        solve(m, r, col);
    }
}

vector<int> find_colours(int N, vector<int> x, vector<int> y){
    n = N;
    v.resize(n);
    d.resize(n, vector<int>(n + 1, -1));
    for(int i = 0; i < x.size(); i++){
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    c.resize(n);
    c[0] = get(0);
    for(int i = 0; i < n; i++){
        solve(1, n, i);
    }
    return c;
}

#ifdef lisie_bimbi

int main() {
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    assert(2 == scanf("%d%d", &N, &M));
    C.resize(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &C[i]));
    X.resize(M), Y.resize(M);
    for (int j = 0; j < M; j++)
        assert(2 == scanf("%d%d", &X[j], &Y[j]));
    fclose(stdin);

    adj.assign(N, std::vector<int>());
    for (int j = 0; j < M; j++) {
        adj[X[j]].push_back(Y[j]);
        adj[Y[j]].push_back(X[j]);
    }

    calls_cnt = 0;
    std::vector<int> G = find_colours(N, X, Y);

    int L = G.size();
    printf("%d %d\n", L, calls_cnt);
    for (int i = 0; i < L; i++)
        printf("%s%d", (i == 0 ? "" : " "), G[i]);
    printf("\n");
    fclose(stdout);

    return 0;
}

#endif

/*
signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    

    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
  
}
*/