EGG Club Training

Cho trước một hoán vị gồm n phần tử và m phép đổi chỗ 2 phần tử. Nhiệm vụ của bạn là thực hiện các phép đổi chỗ một cách hợp lý, sao cho thu được hoán vị thỏa mãn là dãy số tăng dần (tức là dãy hoán vị 1, 2, 3, ... n).

Input

Dòng đầu tiên là 2 số nguyên n (1 <= n <= 12) và m (1 <= m <= n*(n-1)/2) tương ứng là số phần tử và số phép đổi chỗ.

Dòng thứ 2 gồm n số là một hoán vị của dãy 1,2,..., n.

M dòng tiếp theo, dòng thứ i gồm 2 số A_i và B_i, có nghĩa là phép biến đổi thực hiện đổi chỗ số thứ A_i và B_i. Các phép đổi chỗ là riêng biệt.

Input luôn được đảm bảo có đáp án.

Output

In ra một số nguyên duy nhất là số lần thực hiện các phép biến đổi ít nhất.

Example

Test 1:

Input:

2 1

2 1

1 2

Output:

1

Test 2:

Input:

3 2

2 1 3

1 3

2 3

Output:

3

Giải thích test 2:

Thứ tự thực hiện các phép đổi chỗ là 2 1 2.

Test 3:

Input:

5 5 

1 2 3 4 5 

1 5 

2 5 

1 4 

1 1 

3 5

Output:

0