#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int t, n, m, sum;
int fa[1000010], sz[1000010];
vector<int> vec[1000010];
int find(int x) {
  if (x == fa[x])
    return x;
  else
    return fa[x] = find(fa[x]);
}
int main() {
  ios_base::sync_with_stdio(false);
  t = 1;
  while (t--) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
      vec[i].clear();
      sz[i] = 0;
      fa[n + i] = n + i;
    }
    for (int i = 1; i <= n; ++i) {
      int x;
      cin >> x;
      sz[x + n]++;
      vec[x + n].push_back(i);
      fa[i] = x + n;
    }
    sum = 0;
    for (int i = 2; i <= n; ++i) {
      if (find(i) == find(i - 1)) {
        sum++;
      }
    }
    cout << n - sum - 1 << "\n";
    for (int i = 1; i <= m - 1; ++i) {
      int x, y;
      cin >> x >> y;
      int fx = find(x + n), fy = find(y + n);
      if (sz[fx] < sz[fy]) {
        for (int j = 0; j < vec[fx].size(); ++j) {
          if ((vec[fx][j] > 1 && find(vec[fx][j] - 1) == fy)) sum++;
          if ((vec[fx][j] < n && find(vec[fx][j] + 1) == fy)) sum++;
          vec[fy].push_back(vec[fx][j]);
          sz[fy]++;
        }
        sz[fx] = 0;
        fa[fx] = fy;
      } else {
        for (int j = 0; j < vec[fy].size(); ++j) {
          if ((vec[fy][j] > 1 && find(vec[fy][j] - 1) == fx)) sum++;
          if ((vec[fy][j] < n && find(vec[fy][j] + 1) == fx)) sum++;
          vec[fx].push_back(vec[fy][j]);
          sz[fx]++;
        }
        sz[fy] = 0;
        fa[fy] = fx;
      }
      cout << n - sum - 1 << "\n";
    }
  }
  return 0;
}
