Description

It was recently reported that, on the average, only 19 clicks are necessary to move from any page on the World Wide Web to any other page. That is, if the pages on the web are viewed as nodes in a graph, then the average path length between arbitrary pairs of nodes in the graph is 19.

Given a graph in which all nodes can be reached from any starting point, your job is to find the average shortest path length between arbitrary pairs of nodes. For example, consider the following graph. Note that links are shown as directed edges, since a link from page a to page b does not imply a link from page b to page a.

The length of the shortest path from node 1 to nodes 2, 3, and 4 is 1,1, and 2 respectively. From node 2 to nodes 1, 3 and 4, the shortest paths have lengths of 3, 2, and 1. From node 3 to nodes 1, 2, and 4, the shortest paths have lengths of 1, 2, and 3. Finally, from node 4 to nodes 1, 2, and 3 the shortest paths have lengths of 2, 3, and 1. The sum of these path lengths is 1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22. Since there are 12 possible pairs of nodes to consider, we obtain an average path length of 22/12, or 1.833 (accurate to three fractional digits).

Input

The input data will contain multiple test cases. Each test case will consist of an arbitrary number of pairs of integers, a and b, each representing a link from a page numbered a to a page numbered b. Page numbers will always be in the range 1 to 100. The input for each test case will be terminated with a pair of zeroes, which are not to be treated as page numbers. An additional pair of zeroes will follow the last test case, effectively representing a test case with no links, which is not to be processed. The graph will not include self-referential links (that is, there will be no direct link from a node to itself), and at least one path will exist from each node in the graph to every other node in the graph.

Output

For each test case, determine the average shortest path length between every pair of nodes, accurate to three fractional digits. Display this length and the test case identifier (they're numbered sequentially starting with 1) in a form similar to that shown in the sample output below.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

At the Department for Bills and Coins, an extension of today's monetary system has newly been proposed, in order to make it fit the new economy better. A number of new so called e-coins will be produced, which, in addition to having a value in the normal sense of today, also have an InfoTechnological value. The goal of this reform is, of course, to make justice to the economy of numerous dotcom companies which, despite the fact that they are low on money surely have a lot of IT inside. All money of the old kind will keep its conventional value and get zero InfoTechnological value.

To successfully make value comparisons in the new system, something called the e-modulus is introduced. This is calculated as SQRT(X*X+Y*Y), where X and Y hold the sums of the conventional and InfoTechnological values respectively. For instance, money with a conventional value of $3 altogether and an InfoTechnological value of $4 will get an e-modulus of $5. Bear in mind that you have to calculate the sums of the conventional and InfoTechnological values separately before you calculate the e-modulus of the money.

To simplify the move to e-currency, you are assigned to write a program that, given the e-modulus that shall be reached and a list of the different types of e-coins that are available, calculates the smallest amount of e-coins that are needed to exactly match the e-modulus. There is no limit on how many e-coins of each type that may be used to match the given e-modulus.

Input

A line with the number of problems n (0<n<=100), followed by n times:

• A line with the integers m (0<m<=40) and S (0<S<=300), where m indicates the number of different e-coin types that exist in the problem, and S states the value of the e-modulus that shall be matched exactly.
• m lines, each consisting of one pair of non-negative integers describing the value of an e-coin. The first number in the pair states the conventional value, and the second number holds the InfoTechnological value of the coin.

When more than one number is present on a line, they will be separated by a space. Between each problem, there will be one blank line.

Output

The output consists of n lines. Each line contains either a single integer holding the number of coins necessary to reach the specified e-modulus S or, if S cannot be reached, the string "not possible".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Since we all rely on mother earth, it's our duty to save her. Therefore, you're now asked to save energy by switching lights off.

A friend of yours has the following problem in his job. There's a grid of size 10x10, where each square has a light bulb and a light switch attached to it. Unfortunately, these lights don't work as they are supposed to. Whenever a switch is pressed, not only its own bulb is switched, but also the ones left, right, above and under it. Of course if a bulb is on the edge of the grid, there are fewer bulbs switched.

When a light switches it means it's now on if it was off before and it's now off if it was on before. Look at the following examples, which show only a small part of the whole grid. They show what happens if the middle switch is pressed. "O" stands for a light that's on, "#" stands for a light that's off.

###      #O#
###  ->  OOO
###      #O#

###      #O#
OOO  ->  ###
###      #O#

Your friend loves to save energy and asks you to write a program that finds out if it is possible to turn all the lights off and if possible then how many times he has to press switches in order to turn all the lights off.

Input

There are several test cases in the input. Each test case is preceded by a single word that gives a name for the test case. After that name there follow 10 lines, each of which contains a 10-letter string consisting of "#" and "O". The end of the input is reached when the name string is "end".

Output

For every test case, print one line that consists of the test case name, a single space character and the minimum number of times your friend has to press a switch. If it is not possible to switch off all the lights or requires more than 100 presses then the case name should be followed by space and then a -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Tomy's fond of a game called 'Fans and Gems' (also known as Gravnic). In the game, he can use fans to collect gems, but he's satisfied with his play only if all the gems are collected with minimal number of steps. The game is played as following:

There are three kinds of gems, one colored red, one colored green and one colored blue. There are walls in the space, as you see. There are also virtual fans everywhere in the game, but you cannot see them. What you can do each time is to select a DIRECTION to which the fans should blow. There are only four directions possible: UP, DOWN, LEFT and RIGHT. Then, the fans will work, pushing all the gems to fly to the selected direction at the same speed, until they cannot move further(blocked by the wall, other gems or a flyer). Then, if there are some gems touching some same-colored gem(touching means adjacent in one of the four directions), they disappear simultaneously. Note that the fans are still working, so some gems may go on moving in that direction after some gems disappeared. The fans stop working when all the gems cannot move any more, and none of them should disappear. There may be some flyers that can be moved by the fans, but they can NEVER disappear.

You are to write a program that finds the minimal number of operations to make all the gems disappear.

Input

The input file begins with an integer T, indicating the number of test cases. (1 ≤ T ≤ 15) Each test case begins with two integers N, M, indicating the height and width of the map. (1 ≤ N ≤ 12, 1 ≤ M ≤ 20) In the following N lines, each line contains M characters describing the map. There is one line after each map, ignore them. Spaces denotes empty square, '#' denotes a wall, '1' denotes a red gem, '2' denotes a green gem, '3' denotes a blue gem, and '@' denotes a flyer. It's guaranteed that the four sides of the map are all walls. There is at least one gem in the map, and no two same-colored gems will touch each other at the beginning of the game.

Output

You should print a single line for each case. If there is a solution, write the shortest operation sequence in a string. The ith character must be from the set {'U','D','L','R'}, describing ith operation. The four characters represent UP, DOWM, LEFT, RIGHT respectively. If there are more than one solution, choose the lexicographical smallest one, if there are no solution, output -1 on the line. When a solution exists, you need only 18 or fewer steps to carry it out.

Sample Input  Download

Sample Output  Download

Tags

Discuss