机关

题目背景

Steve成功降落后,在M星上发现了一扇大门,但是这扇大门是锁着的

题目描述

这扇门上有一个机关,上面一共有12个旋钮,每个旋钮有4个状态,将旋钮的状态用数字$1$到$4$表示 每个旋钮只能向一个方向旋转(状态:1->2->3->4->1),在旋转时,会引起另一个旋钮也旋转一次(方向相同,不会引起连锁反应),同一旋钮在不同状态下,可能会引起不同的旋钮旋转(在输入中给出) 当所有旋钮都旋转到状态1时,机关就打开了 由于旋钮年久失修,旋转一次很困难,而且时间很紧迫,因此Steve希望用最少的旋转次数打开机关 这个任务就交给你了

输入输出格式

输入格式


$12$行,每行$5$个整数,描述机关的状态 第$i$行第一个整数$s_i$表示第$i$个旋钮的初始状态是$s_i$ 接下来$4$个整数$a_{i,j},j=1,2,3,4$表示这个旋钮在状态$j$时旋转,会引起第$a_{i,j}$个旋钮旋转到下一个状态

输出格式


第一行一个整数$n$,表示最少的步数 第二行$n$个整数,表示依次旋转的旋钮编号 数据保证有解

输入输出样例

输入样例 #1

3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10

输出样例 #1

6
1 2 3 4 5 6

输入样例 #2

3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10

输出样例 #2

6
1 1 2 3 4 5

输入样例 #3

4 2 2 2 2
4 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

输出样例 #3

1
1

输入样例 #4

4 9 3 4 5 
1 9 8 12 11 
4 7 5 6 12 
3 2 2 11 2 
3 6 8 2 12 
4 8 4 2 11 
2 12 9 5 3 
4 1 1 11 1 
1 1 7 4 1 
4 11 6 12 8 
2 6 3 7 6 
4 3 9 7 10 

输出样例 #4

10
11 4 6 10 7 7 5 9 9 9 

说明

样例1和2输入相同,两个输出都可以通过 样例3解释: ``` 414334 241424 旋转11到状态3,引起3旋转到状态1 411334 241434 旋转4到状态4,引起11旋转到状态4 411434 241444 旋转6到状态1,引起11旋转到状态1 411431 241414 旋转10到状态1,引起8旋转到状态1 411431 211114 旋转7到状态3,引起9旋转到状态2 411431 312114 旋转7到状态4,引起5旋转到状态4 411441 412114 旋转5到状态1,引起12旋转到状态1 411411 412111 旋转9到状态3,引起7旋转到状态1 411411 113111 旋转9到状态4,引起4旋转到状态1 411111 114111 旋转9到状态1,引起1旋转到状态1 111111 111111 ``` 数据保证存在打开机关的方式 每个测试点10分 只要你输出格式正确,输出了正确的步数,并给出了任意一种正确方案,就能得到该测试点的得分 否则,该测试点不得分 数据范围: 测试点 | 所需步数 :-: | :-: 1 | 4| 2|6| 3|8| 4|9| 5|10| 6|11| 7|12| 8|13| 9|15| 10|17|