#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int n, m, u, v;
int f[maxn], ff[maxn];
int ans;
vector<int> b[maxn];
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
int fd(int x) { return x == ff[x] ? x : ff[x] = fd(ff[x]); }
void work(int u, int v) {
  int fl = 1;
  if (b[fd(u)].size() < b[fd(v)].size()) swap(u, v);
  int qq = fd(u), pp = fd(v);
  for (auto p : b[pp]) {
    if (p > 1 && fd(f[p - 1]) == qq) --ans;
    if (p < n && fd(f[p + 1]) == qq) --ans;
    b[qq].push_back(p);
  }
  ff[v] = ff[u] = qq;
  ff[qq] = ff[pp] = qq;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = (1); i <= (n); ++i) cin >> f[i], b[f[i]].push_back(i);
  ans = n - 1;
  for (int i = (1); i <= (m); ++i) ff[i] = i;
  for (int i = (1); i <= (m); ++i) {
    if (!b[i].empty()) {
      auto p = b[i].begin();
      while (p != b[i].end()) {
        int st = *p;
        ++p;
        if (p != b[i].end() && *p == st + 1) --ans;
      }
    }
  }
  cout << ans << endl;
  for (int i = (1); i <= (m - 1); ++i) {
    cin >> u >> v;
    work(u, v);
    cout << ans << endl;
  }
  return 0;
}
