#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int arr[maxn];
vector<int> pos[maxn];
int sz[maxn], f[maxn];
int n, m;
int ufind(int x) { return x == f[x] ? x : f[x] = ufind(f[x]); }
int main() {
  scanf("%d%d", &n, &m);
  fill(sz + 1, sz + 1 + m, 0);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    pos[arr[i]].emplace_back(i);
    ++sz[arr[i]];
  }
  int ans = n - 1;
  for (int i = 2; i <= n; i++) {
    if (arr[i] == arr[i - 1]) --ans;
  }
  printf("%d\n", ans);
  for (int i = 1; i <= m; i++) f[i] = i;
  int q = m - 1;
  while (q--) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (sz[a] > sz[b]) {
      for (auto& v : pos[b]) {
        if (v > 1 && ufind(arr[v - 1]) == ufind(a)) --ans;
        if (v < n && ufind(arr[v + 1]) == ufind(a)) --ans;
      }
      for (auto& v : pos[b]) {
        arr[v] = a;
        pos[a].emplace_back(v);
      }
      vector<int>().swap(pos[b]);
    } else {
      for (auto& v : pos[a]) {
        if (v > 1 && ufind(arr[v - 1]) == ufind(b)) --ans;
        if (v < n && ufind(arr[v + 1]) == ufind(b)) --ans;
      }
      for (auto& v : pos[a]) pos[b].emplace_back(v);
      swap(pos[a], pos[b]);
      vector<int>().swap(pos[b]);
    }
    sz[ufind(a)] += sz[ufind(b)];
    f[ufind(b)] = ufind(a);
    printf("%d\n", ans);
  }
  return 0;
}
