Giải bài trực tuyến

"Sắp xếp" là một trò chơi Flash đang thịnh hành hiện nay. Trong trò chơi này, người chơi được cho một hoán vị của các số từ 1 đén N và một dãy các phép tráo đổi. Sau đó, anh ta phải sử dụng các phép tráo đổi này để biến hoán vị ban đầu thành dãy 1, 2, 3, ..., N.

Để phá được kỉ lục, bạn cần phải sử dụng ít phép tráo đổi nhất. Bạn không thể làm được, nhưng bạn có thể lập trình ra một chương trình giúp bạn thực hiện điều đó!

Input

• Dòng thứ 1: Ghi 2 số nguyên N (1 ≤ N ≤ 12), độ dài của dãy số, và M (1 ≤ M ≤ N*(N-1)/2), số các phép biến đổi.

• Dòng thứ 2: Ghi một hoán vị các số nguyên từ 1 đến N.
• M dòng tiếp theo: Mỗi dòng mô tả một phép tráo đổi. Nếu dòng đó ghi hai số nguyên A và B thì bạn có thể hoán đổi vị trí của 2 số ở vị trí thứ A và vị trí thứ B cho nhau trong dãy số. Sẽ không có 2 phép biến đổi nào giống nhau.

Chú ý: Input luôn đảm bảo tồn tại một dãy các phép tráo đổi thỏa mãn đề bài.

Output

• Gồm 1 dòng duy nhất: Ghi ra số phép biến đổi ít nhất cần sử dụng.

Example

Input:
3 2
2 1 3
1 3
2 3

Output:
3