Description

    A group of commandos were assigned a critical task.

    They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task is done.

    In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings.

    You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.

Input

    The first line of input contains a number T ≤ 100, where T denotes the number of test cases.

    Each case describes one head quarter scenario. The first line of each case starts with a positive integer N (1<=N<=1000), where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, 1 ≤ R ≤ N*(N-1)/2, where R is the number of roads connecting two buildings. Each of the next R lines contains two distinct numbers, 0 ≤ u, v < N, this means there is a road connecting building u to building v. The buildings are numbered from 0 to N − 1. The last line of each case contains two integers 0 ≤ s, d < N. Where s denotes the building from where the mission starts and d denotes the building where they must meet.

    You may assume that two buildings will be directly connected by at most one road. The input will be such that, it will be possible to go from any building to another by using one or more roads.

Output

    For each case of input, there will be one line of output. It will contain the case number followed by the minimum time required to complete the mission. Look at the sample output for exact formatting.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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 page 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 node 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 node 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 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. Notice that there is at most one link from a page a to another page b. 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 renumbered 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

    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’.

    The length of the name string is less than 20.

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 al 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

    There are black and white knights on a 5 by 5 chessboard. There are twelve of each color, and there is one square that is empty. At any time, a knight can move into an empty square as long as it moves like a knight in normal chess (what else did you expect?).

    Given an initial position of the board, the question is: what is the minimum number of moves in which we can reach the final position which is:

Input

    First line of the input file contains an integer N that indicates how many sets of inputs are there. The description of each set is given below:

    Each set consists of five lines; each line represents one row of a chessboard. The positions occupied by white knights are marked by ‘0’ and the positions occupied by black knights are marked by ‘1’. The space corresponds to the empty square on board.

    There is no blank line between the two sets of input.

    Note: The first set of the sample input below corresponds to this configuration:

 

Output

    For each set your task is to find the minimum number of moves leading from the starting input configuration to the final one. If that number is bigger than 16, then output one line stating

Unsolvable in less than 17 move(s).

    otherwise output one line stating

Solvable in n move(s).

    where n ≤ 16.

The output for each set is produced in a single line as shown in the sample output.

Case #1: N≤20. Guaranteed that all input can be reached within 3 moves.

Case #2: N≤20. Guaranteed that all input can be reached within 5 moves.

Case #3: N≤20. Guaranteed that all input can be reached within 7 moves.

Case #4: N≤50. At least 20 input cannot be reached within 16 moves.

    Hint 1: Use 2-way BFS + hashtable

    Hint 2: The starting state can reach at most 15000 distinct states within 8 moves in the testcase.

Sample Input  Download

Sample Output  Download

Tags

Discuss