#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
template <class T>
inline T gcd(T a, T b) {
  return !a ? b : gcd(b % a, a);
}
template <class T>
inline T lcm(T a, T b) {
  return (a * b) / gcd(a, b);
}
mt19937 rnd(time(0));
const int N = 2e5 + 2;
int n, m, TOT = 0;
vector<int> parent(N, -1), who(N, -1);
vector<vector<int>> cnt(N, vector<int>());
int findSet(int v) {
  if (parent[v] == v) {
    return v;
  }
  return parent[v] = findSet(parent[v]);
}
void unite(int a, int b) {
  a = findSet(a);
  b = findSet(b);
  if (a != b) {
    if ((int)cnt[a].size() < (int)cnt[b].size()) {
      swap(a, b);
    }
    for (int cur : cnt[b]) {
      if (cur > 1 && who[cur - 1] == a) {
        TOT--;
      }
      if (cur < n && who[cur + 1] == a) {
        TOT--;
      }
    }
    for (int cur : cnt[b]) {
      cnt[a].push_back(cur);
      who[cur] = a;
    }
    parent[b] = a;
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    parent[i] = i;
  }
  TOT = n - 1;
  for (int i = 1; i <= n; i++) {
    cin >> who[i];
    cnt[who[i]].push_back(i);
    if (i > 1 && who[i] == who[i - 1]) {
      TOT--;
    }
  }
  cout << TOT << '\n';
  for (int it = 1; it < m; it++) {
    int u, v;
    cin >> u >> v;
    unite(u, v);
    cout << TOT << '\n';
  }
  return;
}
signed main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int t = 1;
  while (t-- > 0) {
    solve();
  }
  return 0;
}
