// qdd on Feb 20, 2023

#ifdef qdd
#include <ringo>
#else
#include <bits/stdc++.h>
#define dbg(...)
#define dbgr(x, y)
#endif

using namespace std;

using ll = long long;

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v) is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool f = 0;
  for (const T& x : v) (f ? os << ' ' : os) << x, f = 1;
  return os;
}

const int N = 2e5 + 5;

int p[N];

struct dsu {
  vector<int> p;
  dsu(int n) : p(n, -1) {}
  int find(int x) { return (p[x] < 0) ? x : p[x] = find(p[x]); }
  bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return 0;
    p[y] += p[x];
    p[x] = y;
    return 1;
  }
};

void sol() {
  int n, q;
  cin >> n >> q;
  dsu d(n + 1);
  int cycles = n, in_place = 0, in_parity = 0;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    if (d.merge(i, p[i])) cycles--;
    if (p[i] == i) in_place++;
    if (p[i] % 2 == i % 2) in_parity++;
  }
  for (int i = 1; i <= q; i++) {
    int u, v;
    cin >> u >> v;
    if (p[u] == u) in_place--;
    if (p[u] % 2 == u % 2) in_parity--;
    if (p[v] == v) in_place--;
    if (p[v] % 2 == v % 2) in_parity--;
    swap(p[u], p[v]);
    int ans;
    if (p[u] == u) in_place++;
    if (p[u] % 2 == u % 2) in_parity++;
    if (p[v] == v) in_place++;
    if (p[v] % 2 == v % 2) in_parity++;
    if (in_place == n) {
      ans = -1;
    } else if (i % 2 == cycles % 2) {
      ans = n;
    } else if (in_parity == n) {
      ans = n - 2;
    } else {
      ans = n - 1;
    }
    cout << ans << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  sol();
  return 0;
}