#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p);
template <class T>
ostream &operator<<(ostream &os, vector<T> &v);
template <class T>
ostream &operator<<(ostream &os, set<T> &v);
inline void optimizeIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}
const int nmax = 2e5 + 7;
struct Graph {
  int n;
  bool dir;
  vector<vector<int>> adj;
  vector<int> parent;
  vector<int> L;
  vector<vector<int>> sptable;
  Graph(int n, bool dir) {
    this->n = n;
    this->dir = dir;
    int len = n + 1;
    adj = vector<vector<int>>(len);
    parent = vector<int>(len);
    L = vector<int>(len);
  }
  void add_edge(int u, int v) {
    adj[u].push_back(v);
    if (!dir) adj[v].push_back(u);
  }
  void dfs(int u, int par, int lvl) {
    ;
    parent[u] = par;
    L[u] = lvl;
    for (int v : adj[u]) {
      if (v != par) dfs(v, u, lvl + 1);
    }
  }
  void lca_init() {
    sptable = vector<vector<int>>(n + 1, vector<int>(20, -1));
    for (int i = 1; i <= n; i++) sptable[i][0] = parent[i];
    for (int j = 1; (1 << j) < n; j++)
      for (int i = 1; i <= n; i++)
        if (sptable[i][j - 1] != -1)
          sptable[i][j] = sptable[sptable[i][j - 1]][j - 1];
  }
  int Lift(int node, int level) {
    int log;
    for (log = 1; (1 << log) <= L[node]; log++)
      ;
    log--;
    for (int i = log; i >= 0; i--)
      if (level & (1 << i)) node = sptable[node][i];
    return node;
  }
  int lca_query(int u, int v) {
    if (L[u] < L[v]) swap(u, v);
    int dis = L[u] - L[v];
    u = Lift(u, dis);
    if (u == v) return u;
    int log;
    for (log = 1; (1 << log) <= L[u]; log++)
      ;
    log--;
    for (int i = log; i >= 0; i--)
      if (sptable[u][i] != -1 && sptable[v][i] != -1 &&
          sptable[u][i] != sptable[v][i]) {
        u = sptable[u][i];
        v = sptable[v][i];
      }
    return parent[u];
  }
  void debug() {
    for (int i = 1; i <= n; i++) {
      cout << "Node " << i << " : ";
      for (int v : adj[i]) cout << v << " ";
      cout << "\n";
    }
  }
};
void solveTC() {
  int n, t;
  cin >> n >> t;
  vector<int> tower(n + 1);
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    tower[i] = x;
  }
  Graph g(2 * t - 1, false);
  int id = t;
  vector<int> cur(n + 1);
  for (int i = 1; i <= n; i++) cur[i] = i;
  for (int q = 1; q < t; q++) {
    int a, b;
    cin >> a >> b;
    int now = ++id;
    g.add_edge(now, cur[a]);
    g.add_edge(now, cur[b]);
    cur[a] = now;
    cur[b] = now;
    ;
  };
  int root = id;
  g.dfs(root, -1, 0);
  g.lca_init();
  vector<int> pre(t);
  for (int i = 1; i < n; i++) {
    int l = g.lca_query(tower[i], tower[i + 1]);
    ;
    if (l <= t)
      pre[0]++;
    else
      pre[l - t]++;
  };
  for (int i = 1; i < t; i++) pre[i] += pre[i - 1];
  for (int x : pre) cout << n - 1 - x << "\n";
}
int32_t main() {
  optimizeIO();
  int tc = 1;
  while (tc--) {
    solveTC();
  }
  return 0;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
  os << "{" << p.first << ", " << p.second << "} ";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, vector<T> &v) {
  os << "[ ";
  for (T i : v) {
    os << i << " ";
  }
  os << " ]";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, set<T> &v) {
  os << "[ ";
  for (T i : v) {
    os << i << " ";
  }
  os << " ]";
  return os;
}
