题目描述

给定一个 $1$ 到 $n$ 的排列 $p_1,p_2,\dots,p_n$，再给定 $m$ 种交换操作，每种操作由两个位置 $a_i,b_i$ 组成，表示可以将排列上第 $a_i$ 个位置上的数字与第 $b_i$ 个位置上的数字交换。

请问至少需要几步交换操作，才能将这个排列变成 $1,2,\dots,n$？保证解法一定存在且不会超过 $13$ 步。

输入格式

• 第一行：两个整数 $n$ 和 $m$
• 第二行：$n$个整数表示 $p_1$ 到 $p_n$
• 第三行到第$m+2$行：第 $i+1$ 行有两个整数表示 $a_i$ 和 $b_i$

输出格式

单个整数：表示最少需要多少次交换

3 2
2 1 3
1 3
2 3

3

数据范围

• $1\leq n\leq 12$
• $1\leq m\leq 45$
• $1\leq p_1,\dots,p_n\leq n$
• $1\leq a_i, b_i\leq n$
• 保证答案不超过$13$