#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<int> t(n);
  for (auto& id : t) {
    scanf("%d", &id);
    --id;
  }
  int dif = 0;
  for (int i = 0; i + 1 < n; ++i) {
    if (t[i] != t[i + 1]) {
      ++dif;
    }
  }
  auto upd = [&](int id, int val) {
    if (id > 0 && t[id] != t[id - 1]) {
      --dif;
    }
    if (id + 1 < n && t[id] != t[id + 1]) {
      --dif;
    }
    t[id] = val;
    if (id > 0 && t[id] != t[id - 1]) {
      ++dif;
    }
    if (id + 1 < n && t[id] != t[id + 1]) {
      ++dif;
    }
  };
  vector<int> p(m);
  vector<vector<int>> ids(m);
  for (int i = 0; i < m; ++i) {
    p[i] = i;
  }
  for (int i = 0; i < n; ++i) {
    ids[t[i]].push_back(i);
  }
  function<int(int)> getId = [&](int v) -> int {
    if (p[v] == v) {
      return v;
    }
    p[v] = getId(p[v]);
    return p[v];
  };
  auto mergeIds = [&](int v, int u) {
    v = getId(v);
    u = getId(u);
    if (v != u) {
      if ((int)(ids[v]).size() > (int)(ids[u]).size()) {
        swap(v, u);
      }
      p[v] = u;
      for (auto id : ids[v]) {
        upd(id, u);
        ids[u].push_back(id);
      }
      return true;
    }
    return false;
  };
  printf("%d\n", dif);
  for (int it = 0; it + 1 < m; ++it) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a;
    --b;
    assert(mergeIds(a, b));
    printf("%d\n", dif);
  }
  return 0;
}
