Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P142PROB - ROUND 2B - Swap

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

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


Được gửi lên bởi:adm
Ngày:2014-02-08
Thời gian chạy:1.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 JAVA PAS-FPC PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.