#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

void solve() {
  int n, q;
  cin >> n >> q;
  
  vector<int> a(n + 1);
  
  int count_ci_odd = 0;
  int count_i_pi_same = 0;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    
    if (a[i] % 2 != i % 2) {
      count_ci_odd++;
    }
    
    if (a[i] == i) {
      count_i_pi_same++;
    }
  }
  
  vi visited(n + 1);
  int even_cycle_cnt = 0;
  for(int i = 1; i <= n; i++) {
    if (visited[i]) continue;
    int curr = i;
    int cycle_size = 0;
    while (!visited[curr]) {
      visited[curr] = 1;
      cycle_size++;
      curr = a[curr];
    }
    if (cycle_size % 2 == 0) {
      even_cycle_cnt++;
    }
  }
  
  // sorted parity is even
  // current parity = even_cycle_cnt * odd (: even_cycle_size - 1) + x * even
  int current_parity = even_cycle_cnt % 2;

  while (q--) {
    int i, j;
    cin >> i >> j;
    
    if (a[i] % 2 != i % 2) {
      count_ci_odd--;
    }
    if (a[i] == i) {
      count_i_pi_same--;
    }
    if (a[j] % 2 != j % 2) {
      count_ci_odd--;
    }
    if (a[j] == j) {
      count_i_pi_same--;
    }
    swap(a[i], a[j]);
    if (a[i] % 2 != i % 2) {
      count_ci_odd++;
    }
    if (a[i] == i) {
      count_i_pi_same++;
    }
    if (a[j] % 2 != j % 2) {
      count_ci_odd++;
    }
    if (a[j] == j) {
      count_i_pi_same++;
    }
    
    // parity change by 1 for each swap
    current_parity = (current_parity + 1) % 2;
    if (current_parity == 1) {
      cout << n << endl;
      continue;
    }
    if (count_ci_odd >= 1) {
      // remove any odd contribution
      cout << n - 1 << endl;
      continue;
    }
    if (count_i_pi_same == n) {
      // all even, and they are sorted
      cout << -1 << endl;
      continue;
    }
    // remove two even contributions which are out of order
    cout << n - 2 << endl;
    continue;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  solve();
  
  return 0;
}