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.|

POSLOZI - POSLOZI

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/poslozi


"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

Được gửi lên bởi:khanhptnk
Ngày:2009-11-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:COCI contest 2, problem 5

hide comments
2019-10-07 16:36:30
A* <(")

Last edit: 2019-10-07 17:21:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.