XXX的机器人

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 65536/32768KB (Java/Others)

Problem Description

XX手里有5张卡片,卡片上的数字分别是1~5的某个全排列a[l], a[2], a[3], a[4], a[5](比如2 3 1 5 4)。

有n个房间。每个房间都有一个卡片转化规则,每个规则也是1~5的某个全排列b[l], b[2], b[3], b[4], b[5](比如 3 4 2 1 5)。

每进入到一个房间手里的卡片会根据当前房间的规则做相应的变换:a[i] = b[ a[i] ] (1 <= i <= 5)。

相邻的两个房间是相连的,也就是说第i个房间可以走到i+1房间和i-1房间(如果i+1房间和i-1房间存在的话)。

XX的目标是使手里的卡片变成1 2 3 4 5。

由于XX要和奶茶妹妹约会,没有时间,所有他派遣一个机器人去帮他。并且写了m条指令。

每一条指令的格式是S T, 表示从S房间走到T房间。

这m条指令只能按顺序执行。对于每条指令机器人可以选择执行或不执行。

这个机器人想知道最少要路过多少个房间可以达到XX的要求。

Input

输入有多组数据,对于每组数据:
      第一行为两个数字n, m(2<=n<=100000,  0<= m <= 100),表示有n个房间,有m条指令。

接下来有n行,每行5个数字(为1~5的某个全排列),表示每一个房间的转换规则。

然后有m行,每一行有两个数字S, T( 1<=S, T<=n, S != T)表示每条指令。

最后一行有5个数字(为1~5的某个全排列),表示XX初始时手里的卡片。

Output

对于每组数据,输出最小值。如果没有满足条件的最小值,那么输出-1。

 

Sample Input

2 2
1 5 2 3 4
1 3 5 2 4
2 1
2 1
1 2 4 5 3

Sample Output

4

Hint

只有这两条指令都执行才能达到要求,所以要路过4个房间

Source

zju_xxx

Manager

Information
Solved Number19
Submit Number63
Problem Tags
dp
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel