Description

In our increasingly interconnected world, it has been speculated that everyone on Earth is related to everyone else by no more than six degrees of separation. In this problem, you must write a program to find the maximum degree of separation for a network of people.

For any two people, the degree of separation is the minimum number of relationships that must be traversed to connect the two people. For a network, the maximum degree of separation is the largest degree of separation between any two people in the network. If there is a pair of people in the network who are not connected by a chain of relationships, the network is disconnected.

As shown below, a network can be described as a set of symmetric relationships each of which connects two people. A line represents a relationship between two people. Network A illustrates a network with 2 as the maximum degree of separation. Network B is disconnected.

Network A: Max. degree of separation = 2 Network B: Disconnected

Input

The input consists of data sets that describe networks of people. For each data set, the first line has two integers: P (2≤P≤50), the number of people in the network, and R (R≥1), the number of network relationships. Following that first line are R relationships. Each relationship consists of two strings that are names of people in the network who are related. Names are unique and contain no blank spaces. Because a person may be related to more than one other person, a name may appear multiple times in a data set.

The final test case is followed by a line containing two zeroes.

Output

For each network, display the network number followed by the maximum degree of separation. If the network is disconnected, display `DISCONNECTED'. Display a blank line after the output for each network. Use the format illustrated in the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are a technician for the Air Conditioning Machinery company (ACM). Unfortunately, when you arrive at a customer site to install some air conditioning ducts, you discover that you are running low on supplies. You have only six duct segments, and they are all of the same kind, called an ``elbow.''

You must install a duct in a confined space: a rectangular prism whose sides are multiples of a unit length. Think of the confined space as consisting of an array of unit cubes. Each elbow occupies exactly four unit cubes, as shown in Figure 1 below. A unit cube can be occupied by at most one elbow. Each elbow has exactly two openings, as indicated by the gray squares in the elbow shown in Figure 1. You may assemble the elbows into longer ducts, but your duct must be completely contained inside the given space. One way to connect two elbows is shown in Figure 2. Your task is to connect an inflow to an outflow. The inflow and the outflow are located on the exterior surface of the confined space, aligned with the unit cubes, as shown in Figure 3. To keep expenses down, you must accomplish this task while using the minimum number of elbows.

Input

The input consists of several test cases, each of which consists of a single line containing eleven input values separated by blanks. The input values for each test case are as follows.

The first three input values are integers (x_max , y_max , and z_max ) that indicate the size of the confined space in the x , y , and z dimensions, respectively. Each unit cube in the confined space can be identified by coordinates (x, y, z) where 1≤x≤x_max , 1≤y≤y_max , and 1≤z≤z_max . x_max , y_max , and z_max are all positive and not greater than 20.

The next three input values are integers that indicate the location of the inflow by identifying the x , y , and z coordinates of the unit cube that connects to the inflow.

The next input value is a two-character string that indicates the direction of the inward flow, using one of the following codes: + x, - x, + y, - y, + z, - z . The inflow connection is on the face of the unit cube that receives this inward flow. For example, if the data specifies an inflow direction of + y , the inflow connection is on the face of the unit cube that faces in the negative y direction.

The next three input values are integers that indicate the location of the outflow by identifying the x , y , and z coordinates of the unit cube that connects to the outflow.

The last input value is a two-character string that indicates the direction of the outward flow, using the same codes described above. The outflow connection is on the face of the unit cube that generates this outward flow. For example, if the data specifies an outflow direction of + y , the outflow connection is on the face of the unit cube that faces in the positive y direction.

The last line of the input file consists of a single zero to indicate end of input.

Output

For each test case, print the case number (starting with 1) followed by the minimum number of elbows that are required to connect the inflow to the outflow without going outside the confined space. If the task cannot be accomplished with your supply of six elbow segments, print the word `Impossible' instead. Use the format in the sample data.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The city of Banff hired an advertising agency to promote the city's attractions to potential visitors. One of the planned slogans stated that the mountain ranges around the city form the most beautiful skyline in Canada. But the Institute for Consumer Protection in Canada (ICPC) decided that ``the most beautiful skyline" was a subjective and unverifiable claim, and could therefore be considered misleading.

The advertising agency then came up with the slogan ``Banff - the longest skyline in Canada." Although not as catchy, it is hopefully verifiable, and therefore admissible under Canada's tricky advertising laws.

This is where you come in. What the advertising agency needs is a program that determines the length of a skyline. Consider each mountain as a two-dimensional triangle having two upper sides the same length. A skyline is the outline of one or more mountains. The skyline's length is the total length of the outline. The left illustration below shows three mountains. The right illustration shows (with bold lines) the skyline and (with dashed lines) the portion of the mountains' upper edges that are not part of the skyline. Note that parts of the horizon line that lie between mountains are not considered part of the skyline.

Input

Each input file contains one or more test cases, which are descriptions of mountain ranges. Each description starts with a line containing a positive integer N , which specifies the number of mountains in the range. Each of the next N lines describes a mountain with three integers X , H , and B , which specify the horizontal position of the mountain's peak relative to some fixed point, the height of the peak, and the width of the base of the mountain, respectively. The base of each mountain coincides with a horizontal line. The values satisfy the conditions N≤100 , H > 0 , and B > 0 .

The last test case is followed by a line containing a zero.

Output

For each test case, print the case number (beginning with 1) and the length of the skyline. Print the length rounded to the nearest integer, with 0.5 rounded up. Print a blank line after the output of each test case. Use the format shown in the sample output below.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

By 2100, space travel will be a reality for the Milky Way (Solar Galaxy) residents. The Interstar Transport Travel agency operates scheduled direct space transports (flights) between some of the most popular planet destinations in the Milky Way. The cost of these scheduled direct transports are predetermined in Galaro (Galaxy Currency unit) and are published in many different languages. For travel to planets that is not on the schedule, there are slower, yet free, space flights from the closest planet that is on the direct transport list. To help travelers plan their itinerary, the Interstar Transport wants to offer a mobile application that can find the best traveling option, based on the total cost of the direct transports on the itinerary. Given the starting and destination planets on the itinerary, find the sequence of direct transports that has the lowest total traveling cost. Output all the planets in sequence that one must pass through on this best route. If two or more routes exist with the same cost, then the route that goes through the least number of intermediate planets is considered a better route. There will always exist a unique best route for any of the given test cases.

Technical Specification

1. The number of planets on the direct transport list is at most s, 1 ≤ s ≤ 26. The planets are labeled using capital letters of the English alphabets, i.e., “A”, “B”, “C”, ..., “Z”, in no particular order.
2. The Interstar Transport operates at most p, 1 ≤ p ≤ 200, direct transports between planets. There is at most one (could be none) direct transport between any two distinct planets.
3. The cost of any transport is given as a natural number less than or equal to 100 Galaros.

Input

The first line of the input file contains two integers, s and p, separated by a space. The next p lines each contains two letters, e_i and e_j , followed by a natural number, d_ij , indicating that there exists a direct transport between planets e_i and e_j with a cost of d_ij . The next line contains an integer n ≤ 20, indicating the number of queries to follow. For each of the next n lines, each line contains two letters e_k and e_m, indicating a user is looking for a best (lowest cost) way to get from planet e_k to planet e_m.

Output

For each of the n queries in the input, output on one line the best route to take, in the sequence of starting planet, the intermediate planets in sequence along the route and the destination planet; all separated by one blank space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dan McAmbi is a member of a crack counter-espionage team and has recently obtained the partial contents of a file containing information vital to his nation's interests. The file had been compressed using Huffman encoding. Unfortunately, the part of the file that Dan has shows only the Huffman codes themselves, not the compressed information. Since Huffman codes are based on the frequencies of the characters in the original message, Dan's boss thinks that some information might be obtained if Dan can reverse the Huffman encoding process and obtain the character frequencies from the Huffman codes. Dan's gut reaction to this is that any given set of codes could be obtained from a wide variety of frequency distributions, but his boss is not impressed with this reasoned analysis. So Dan has come to you to get more definitive proof to take back to his boss.

Huffman encoding is an optimal data compression method if you know in advance the relative frequencies of letters in the text to be compressed. The method works by first constructing a Huffman tree as follows. Start with a forest of trees, each tree a single node containing a character from the text and its frequency (the character value is used only in the leaves of the resulting tree). Each step of the construction algorithm takes the two trees with the lowest frequency values (choosing arbitrarily if there are ties), and replaces them with a new tree formed by joining the two trees as the left and right subtrees of a new root node. The frequency value of the new root is the sum of the frequencies of the two subtrees. This procedure repeats until only one tree is left. An example of this is shown below, assuming we have a file with only 5 characters -- A, B, C, D and E -- with frequencies 10%, 14%, 31%, 25% and 20%, respectively.

After you have constructed a Huffman tree, assign the Huffman codes to the characters as follows. Label each left branch of the tree with a 0 and each right branch with a 1. Reading down from the root to each character gives the Huffman code for that character. The tree above results in the following Huffman codes: A - 010, B - 011, C - 11, D - 10 and E - 00.

For the purpose of this problem, the tree with the lower frequency always becomes the left subtree of the new tree. If both trees have the same frequencies, either of the two trees can be chosen as the left subtree. Note that this means that for some frequency distributions, there are several valid Huffman encodings.

The same Huffman encoding can be obtained from several different frequency distributions: change 14% to 13% and 31% to 32%, and you still get the same tree and thus the same codes. Dan wants you to write a program to determine the total number of distinct ways you could get a given Huffman encoding, assuming that all percentages are positive integers. Note that two frequency distributions that differ only in the ordering of their percentages (for example 30% 70% for one distribution and 70% 30% for another) are not distinct.

Input

The input consists of several test cases. Each test case consists of a single line starting with a positive integer n (2≤n≤20) , which is the number of different characters in the compressed document, followed by n binary strings giving the Huffman encoding of each character. You may assume that these strings are indeed a Huffman encoding of some frequency distribution (though under our additional assumptions, it may still be the case that the answer is 0 -- see the last sample case below).

The last test case is followed by a line containing a single zero.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the number of distinct frequency distributions that could result in the given Huffman codes.

Sample Input  Download

Sample Output  Download

Tags

Discuss