题目描述

「Arrange」是一款非常流行的网络游戏。在游戏中，首先给出 $1$ 到 $N$ 的一个排列，以及一些允许的交换（例如第 $2$ 个数可以和第 $3$ 个数交换）。游戏者需要对初始的排列进行一系列的交换操作，使得最后得到序列 $1,2,\dots,N$。

为了得到高分，需要尽可能减少操作次数。请你求出至少需要多少次操作，并输出方案。

输入格式

第一行两个数 $N$ 和 $M(1\le N\le 12,1\le M\le \frac{N(N–1)}{2})$，表示数列中有 $N$ 个数，一共有 $M$ 种允许的交换操作。

第二行 $N$ 个用空格隔开的整数，是 $1$ 到 $N$ 的一个排列。

接下来 $M$ 行，第 $i$ 行表示第 $i$ 种交换操作，两个数 $A_i$ 和 $B_i$，表示第 $A_i$ 个数可以和第 $B_i$ 个数交换。数据保证不会出现两对同样的交换。

输入数据保证一定存在这样的方案，但方案可能不唯一。

输出格式

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

样例输入

2 1
2 1
1 2

样例输出

1

数据规模与约定

对于所有数据，有 $1\le N\le 12,1\le M\le \frac{N(N–1)}{2}$。