#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ; 
typedef vector<int> vi;
typedef vector < long long > vl ;
typedef unsigned int uint ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 2e5 + 7 ;

int n , q ;
int a[ MAXN ] ;

bool used[ MAXN ] ;
int cnt_eq = 0 ;

int freq[ 2 ][ 2 ] , tot[ 2 ] ;

void rem ( int val , int pos ) {
    if ( val == pos ) { -- cnt_eq ; }
    -- freq[ ( val % 2 ) ][ ( pos % 2 ) ] ;
}
int add ( int val , int pos ) {
    if ( val == pos ) { ++ cnt_eq ; }
    ++ freq[ ( val % 2 ) ][ ( pos % 2 ) ] ;
}

void solve ( ) {
    cin >> n >> q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    int cycles = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( used[ i ] == false ) {
            ++ cycles ;
            int x = i ;
            while ( used[ x ] == false ) {
                used[ x ] = true ;
                x = a[ x ] ;
            }
        }
    }
    tot[ 0 ] = n / 2 ;
    tot[ 1 ] = ( n + 1 ) / 2 ;
    cycles %= 2 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( a[ i ] == i ) { ++ cnt_eq ; }
        ++ freq[ ( a[ i ] % 2 ) ][ ( i % 2 ) ] ;
    }
    while ( q -- ) {
        cycles ^= 1 ;
        int x , y ; cin >> x >> y ;
        rem ( a[ x ] , x ) ; rem ( a[ y ] , y ) ;
        swap ( a[ x ] , a[ y ] ) ;
        add ( a[ x ] , x ) ; add ( a[ y ] , y ) ;
        if ( cnt_eq == n ) { cout << "-1\n" ; }
        else {
            if ( cycles != ( n % 2 ) ) { cout << n << "\n" ; }
            else if ( freq[ 0 ][ 0 ] == tot[ 0 ] && freq[ 1 ][ 1 ] == tot[ 1 ] ) {
                cout << n - 2 << "\n" ;
            }
            else {
                cout << n - 1 << "\n" ;
            }
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}