It seems that our efforts were not in vain,' Alba said after studying an ancient volume.I've found here a method for accumulating a tremendous amount of energy. And the idea is so simple that I wonder why nobody has discovered it. The usual problem is that magic energy is unstable and it's difficult to keep it in one place. But if we channel it along a closed path, it'll have no way out. We only have to choose the right length of the path to keep the flow stable. Then we can pump in as much energy as we want. And when we break the path we'll release a magic flow of enormous power. It'll be a real breakthrough in war magic!'
Yes, but the path must be long enough and you can't drag a large device over a battlefield.'<br>That's not a problem. The form of the path can be arbitrary. We can design a compact scheme of the device. Actually, the device is here already, it's there in the corner. We only have to adjust it.'
Indeed, there was a square grid with n × n nodes. At each node there was a prism that could be turned so as to either direct a flow of magic energy straightly or turn it by 90°. Soren and Alba had to position L prisms so that a cyclic flow of magic energy of length L could be directed through them.
Warn: 本題有 specialjudge
There are many test cases ended with EOF.
For each test case, you are given the integers n and L (2 ≤ n ≤ 100; 4 ≤ L ≤ 20 000).
If it is impossible to organize a cycle of required length, output “Unsuitable device”. Otherwise, output “Overwhelming power of magic” in the first line. In each of the following L lines give two integers in the range from 1 to n, which are the coordinates of the grid nodes through which energy should pass. The distances between two consecutive nodes and between the first and the last nodes must be equal to 1. The energy mustn't pass more than once through the same node, because this may produce unpredictable and, most likely, lethal effects.
2 6 3 6
Unsuitable device Overwhelming power of magic 1 1 2 1 3 1 3 2 2 2 1 2
Migrated from old NTUJ.
NEERC 2012, Eastern subregional contest
| No. | Testdata Range | Score |
|---|