[Coci2009]POSLOZI ]数列整合

时间限制:3s      空间限制:128MB

题目描述

“Arrange”是一款非常流行的网络游戏。在游戏中,首先给出1到N的一个排列,以及一些允许的交换(例如第2个数可以和第3个数交换)。游戏者需要对初始的排列进行一系列的交换操作,使得最后得到序列1,2,……,N。
为了得到高分,需要尽可能减少操作次数。请你求出至少需要多少次操作,并输出方案。
 


输入格式

第一行两个数N和M(1≤N≤12;1≤M≤N*(N–1)/2 ),表示数列中有N个数,一共有M种允许的交换操作。
第二行N个用空格隔开的整数,是1到N的一个排列。
接下来M行,第i行表示第i种交换操作,两个数Ai和Bi,表示第Ai个数可以和第Bi个数交换。数据保证不会出现两对同样的交换。
输入数据保证一定存在这样的方案,但方案可能不唯一。
 


输出格式

第一行一个整数X,表示最少需要操作X次。


样例输入

2 1
2 1
1 2

样例输出

1

提示

没有写明提示


题目来源

没有写明来源