汉诺塔 ## 来源 Zhejiang University Local Contest 2008 (ZOJ2954) ## 题目描述 汉诺塔游戏中有3根柱子（编号分别为1～3）和N个半径大小不等的盘子。初始时，N个盘子位于1号柱子，按照它们的半径大小的顺序叠在一起，最大的盘子在下面、最小的盘子在上面。每轮游戏，可以将某个柱子最上面的盘子移动到另一个柱子上，但自始至终都必须保证每根柱子上都是大盘子在下面、小盘子在上面（或者没有盘子）。游戏的目标是要将所有的盘子移动到3号柱子上。移动步骤用两个不同的整数a和b来表示，1≤a, b≤3，表示将a号柱子上最上面的盘子移动到b号柱子上。一次移动是合法的，当且仅当a号柱子上至少有一个盘子，且a号柱子最上面的盘子能移动到b号柱子上。给定汉诺塔游戏一些移动步骤，求游戏的结果。 ## 输入描述 输入文件包含多个测试数据。第1行为整数T，1≤T≤55，代表测试数据的个数。接下来有T个测试数据。每个测试数据的第1行为两个整数n(1≤n≤10)和m(1≤m≤12000)，分别代表盘子个数和移动步骤数目；接下来有m行，每行描述了一次移动步骤。 ## 输出描述 对每个测试数据，输出一行，为一个整数，含义如下： (1) 如果在将所有盘子移动到3号柱子之前出现了非法的移动，并且第p次移动是非法的（移动步数从1开始计起），输出-p，后面的移动将被忽略。 (2) 如果移动p步后，所有盘子都移动到3号柱子上，且没有非法移动，则输出p，后面的移动将被忽略。 (3) 其他情况输出0。 ## 样例输入 ```txt 3 2 3 1 2 1 3 2 3 2 3 1 2 1 3 3 2 2 3 1 3 1 2 3 2 ``` ## 样例输出 ```txt 3 -3 0 ``` ## 提示 本题只要模拟汉诺塔的m次移动，并判断是否成功完成游戏或出现了非法移动等情形。