1568 . Perfect Hanoi Tower
Description
There are n disks with different radius on three pegs. Your job is to move the disks one by one such that only smaller disks may be put on a larger disk. The goal is to move all the disks from one peg to another. You can solve this in minimum steps, right? perfect! But, unfortunately, you are moving some bombing disks! It is known that, for some specific pairs of disks, when they touch each other, bombbbbb!!!!
What is the minimum steps achieve the goal, or there is no way to do that?
Input Format
First line contains an integer T (T<=100) indicating the number of test cases. For each test case, first line contains two integers n, m (1<=n<=300, 0<=m<=300) denoting the number of disks and number of forbidden pairs. Each of the next m lines contains two integers a, b (1<=a, b<=n, a!=b), denoting disk a and disk b cannot be put together after any move. All pair of integers in the same test case will be different.
Output Format
For each test case, please output the minimum steps to achieve the goal: move all disks from one peg to another. Since the answer may be large, you only need to output the answer modulo 0x19890514. If it is impossible to achieve the goal, output -1.
Sample Input 1
4 5 0 5 1 1 4 5 2 1 3 1 4 300 0
Sample Output 1
31 39 -1 30308703
Hints
Problem Source
Migrated from old NTUJ.
tmt514
Subtasks
| No. | Testdata Range | Score |
|---|