#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

#define MAX 144

int N, M, a;

vector< int > V, c;
queue< vector< int > > Q;
map< vector< int >, int > dist;

int x[ MAX ];
int y[ MAX ];

int main( void )
{
    scanf( "%d%d", &N, &M );
    
    for( int i = 0; i < N; ++i ) {
         scanf( "%d", &a ); --a;
         V.push_back( a );
    }
    
    for( int i = 0; i < M; ++i ) {
         scanf( "%d%d", x+i, y+i );
         --x[i]; --y[i];
    }
    
    Q.push( V );
    dist[ V ] = 1;
    
    while( !Q.empty() ) {
           c = Q.front(); Q.pop();
           
           bool ok = 1;
           
           for( int i = 0; i < N; ++i )
                if( c[i] != i ) { ok = 0; break; }
           
           if( ok ) { printf( "%d\n", dist[ c ] - 1 ); }
           
           int d = dist[ c ];
           
           for( int i = 0; i < M; ++i ) {
                swap( c[x[i]], c[y[i]] );
                
                if( dist[ c ] ) { swap( c[x[i]], c[y[i]] ); continue; }
                dist[ c ] = d + 1;
                
                Q.push( c );
                swap( c[x[i]], c[y[i]] );
           }
    }
    
    return 0;
}