Description

  Walking around the campus has become a part of our life. We attend class in CS building, have a meal in restaurant, and go back to sleep in your dorm.

  Peter thinks that it takes too much time to move between two places. He always wants to reach a place as fast as possible. So he often cuts the corner between two places by passing lawn. However, it is harmful to walk on lawn. Since he doesn’t want to do more harm on lawn, Peter makes a trade-off. He hopes to reach destination without using more than a certain time, so he might not need to pass every short-cut. As a friend of Peter, you want to compute the minimum number of short-cut he has to take to encourage him.

Input

   There are no more than 50 test cases. The first line of each test case contains an integer n, indicating the number of places. (1 ≤ n ≤ 100) The parts are numbered from 1 to n. The second line contains an integer M, indicating the number of roads. Then M lines in the form "a b c", which mean there is a road between the a^th place and the b^th place and takes c minutes to walk along it. Then an integer S and S lines follow, describing the short-cuts with the same way as the roads. The next contains two integers indicating the places to which the start and the destination. The last line contains one integer T, the time limit to reach the destination. (0 ≤ T ≤ 1,000,000,000)

   The roads and the shortcuts are all bidirectional. There is at most one road between any two places. There is at most one shortcut between any two places. The time cost of each road or shortcut do not exceed 1,500,000 but at least 1.

Output

   Output the minimum number of short-cuts Peter has to take in one line. If it’s impossible to reach on time, print “Impossible” in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jisung is the student representative of the Department of Computer Engineering in ACM University. A few days later, the annual festival will be held for the students in the department. He is preparing some events for the festival. Since Jisung likes to make and solve puzzles, he decides to devise some interesting puzzle for the festival.

The followings are the rules for the puzzle made by Jisung:

(1) The players will be given an integer n . Then they should use the first n capital letters from the Roman alphabet. For example, if n = 4, the four characters A, B, C, and D will be used to solve this puzzle.

(2) The players will be given s forbidden strings. No forbidden string contains another forbidden string as a substring. The winner is the student who makes the longest string that does not include a forbidden string as a substring.

(3) If such a longest string does not exist, i.e., if we can make arbitrarily long strings that satisfy the above condition, or if we cannot make any string that satisfies the above condition, “No” should be answered.

For example, suppose the given number n = 2 , i.e., the players can use the two characters A and B. Assume that the forbidden strings are {AAA, AB, BA, BB}. In this case, the longest string that does not include any of the four forbidden strings as substrings is AA. But if the given forbidden strings are {AAA, BBB, ABAB, BBAA}, we cannot make such a longest string since arbitrarily long concatenations of ABA, i.e., ABAABAABA ... do not include any forbidden string.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 26) and s (1 ≤ s ≤ 1, 000) which represent the number of characters and the number of forbidden strings, respectively. From the second line to (s + 1) -st line of the test case, the forbidden strings are given one by one. The length of a forbidden string does not exceed 50.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the longest string that does not include any forbidden string as a substring if it exists, otherwise, just print “No” as output. When there exists more than one such longest string with the same length, print the lexicographically largest string among them.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

During this economic crisis time, Jack has started an incredible new business related to air travel, a parking-lot for airplane. He bought a very large land to park airplanes. However the land is very narrow, so that the only way airplanes can go in or go out of the parking lot must be in the Last-In First-Out fashion (see picture below). He only has spaces in the parking lot so he cannot take some airplane at the end out so that other airplanes can move.

Input

The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.

The first line starts with an integer N (1 < N < 300) denoting the number of airplanes. The next N lines describe the request table. Each line 1 + i, for 1 < i < N, contains two integer Si and Ti , (0 < Si < Ti < 1,000,000,000) which are the planned arrival time and planned departing time for airplane i. 

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

On a small planet named Bandai, a landing party of the starship Tadamigawa discovered colorful cubes traveling on flat areas of the planet surface, which the landing party named beds. A cube appears at a certain position on a bed, travels on the bed for a while, and then disappears. After a longtime observation, a science officer Lt. Alyssa Ogawa of Tadamigawa found the rule how a cube travels on a bed.

A bed is a rectangular area tiled with squares of the same size.

• One of the squares is colored red,
• one colored green,
• one colored blue,
• one colored cyan,
• one colored magenta,
• one colored yellow,
• one or more colored white, and
• all others, if any, colored black.

Initially, a cube appears on one of the white squares. The cube's faces are colored as follows.

The cube can roll around a side of the current square at a step and thus rolls on to an adjacent square. When the cube rolls on to a chromatically colored (red, green, blue, cyan, magenta or yellow) square, the top face of the cube after the roll should be colored the same. When the cube rolls on to a white square, there is no such restriction. The cube should never roll on to a black square.

Throughout the travel, the cube can visit each of the chromatically colored squares only once, and any of the white squares arbitrarily many times. As already mentioned, the cube can never visit any of the black squares. On visit to the final chromatically colored square, the cube disappears. Somehow the order of visits to the chromatically colored squares is known to us before the travel starts.

Your mission is to find the least number of steps for the cube to visit all the chromatically colored squares in the given order.

Input

The input is a sequence of datasets. A dataset is formatted as follows:

w d
c₁₁ .. c_w1
...
c_1d ... c_wd
v₁v₂v₃v₄v₅v₆

The first line is a pair of positive integers w and d separated by a space. The next d lines are w -character-long strings c₁₁ ^... c_w1, ^... , c_1d ^... c_wd with no spaces. Each character c_ij is one of the letters r, g, b, c, m, y, wand k, which stands for red, green, blue, cyan, magenta, yellow, white and black respectively, or a sign #. Each of r, g, b, c, m, y and # occurs once and only once in a dataset. The last line is a six-character-long stringv₁v₂v₃v₄v₅v₆ which is a permutation of ``rgbcmy".

The integers w and d denote the width (the length from the east end to the west end) and the depth (the length from the north end to the south end) of a bed. The unit is the length of a side of a square. You can assume that neither w nor d is greater than 30.

Each character c_ij shows the color of a square in the bed. The characters c₁₁ , c_w1 , c_1d and c_wd correspond to the north-west corner, the north-east corner, the south-west corner and the southeast corner of the bed respectively. If c_ij is a letter, it indicates the color of the corresponding square. If c_ij is a #, the corresponding square is colored white and is the initial position of the cube.

The string v₁v₂v₃v₄v₅v₆ shows the order of colors of squares to visit. The cube should visit the squares colored v₁, v₂, v₃, v₄, v₅ and v₆ in this order. The end of the input is indicated by a line containing two zeros separated by a space.

Output

For each input dataset, output the least number of steps if there is a solution, or ``unreachable" if there is no solution. In either case, print it in one line for each input dataset.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It is 2050 and human live with alien. There are two kind of alien: good alien and evil alien. Good alien were our friend because they help us to develop good technology for our earth. Evil alien were very very bad, they develop heavy and dangerous weapons that can destroy earth. Alien were very hard to kill because of their ultra regeneration skill. Luckily, we have developed a kind of bomb that can kill alien in an instant. This weapon is very expensive so we must use it wisely.

Given a map of 10 × 10, each element in the map will be:

• '.' represents empty region.
• 'g' represents good alien.
• 'e' represents evil alien.

Calculate how many evil alien that can be killed without killing any good alien, and how many bombs we need to do that. A bomb has a 3 × 3 area of effect, so all of the 8 adjacent neighbors will also be destroyed. You can put bomb anywhere in the map, even if there is an alien in that cell. For example,

e..
.Xe
..e

Bombing at X will kill three evil aliens.

Our spy has reported that the number of alien groups from each side is less than 16.

Input

First line in the input will be T (1 ≤ T ≤ 100) number of cases. Each case will have a map of 10 × 10 represent the city. Between each city will be separated by a blank line.

Output

For each case, output two numbers: a and b, where a is the maximum number of evil aliens that you can kill and b is the minimum number of bombs you need to do that.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. Drivers are only allowed to drive up to 10 hours a day. The transport company wants to find a route from the starting city to the destination city such that a driver can always spend the night in one of the hotels of the hotel chain, and that he needs to drive at most 10 hours from one hotel to the next hotel (or the destination). Of course, the number of days needed to deliver the goods should also be minimized.

Input

The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c₁, c₂, ..., c_h indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 10⁵), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.

Output

For each test case, print one line containing the minimum number of hotels the transport company has to book for a delivery from city 1 to city n. If it is impossible to find a route such that the driver has to drive at most 10 hours per day, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alex has a puzzle her father gave her last Christmas. It has nine numbered squares arranged in a 3×3 matrix (three rows and three columns) and it's mechanically designed to allow the following types of movements:

• A horizontal right move shifts one position to the right each of the squares in the corresponding horizontal row (circularly).
• A vertical up move shifts one position upwards each of the squares in the corresponding vertical column (circularly).

Alex's troublemaker little brother Jim snuck last night into his sister's bedroom and somehow tore the puzzle apart and put it back together. However, when Jim assembled the puzzle back, he might have done it in a configuration different from the original configuration of the puzzle.

The next morning, when Alex found her puzzle had been scrambled, she called you to help her to reset her puzzle to its original configuration (shown below) as quickly as possible, so her father won't realize that the puzzle was torn and scrambled. Of course, you should do it using only valid movements, as above described.

Your task is to write a program that, given a configuration, finds a way to set the puzzle to its original configuration spending the minimum possible number of moves to accomplish it, if the given puzzle is solvable. If this is not the case, the program should point it out.

Input

The problem input consists of several cases, each one defined by three lines that describe a puzzle configuration. That is, lines correspond to a top-down description of the rows of the given configuration, and each line consist of three digits, separated by one blank character.

The end of the input is indicated by a line with a number 0.

Output

For each puzzle in the input, you must print a line containing S , the minimum number of moves required to set the puzzle to its original configuration, followed by a space and 2*S characters indicating any sequence of S moves that solves the puzzle.

A move is described by two characters: the first one must be H or V (H specifies a horizontal move, and V a vertical move), and the second one must be 1, 2, or 3 to indicate the row or the column to move.

If the puzzle is not solvable, you must output a line with the text ``Not solvable''.

Hint: Consider each state as a node of the graph, transistion is an edge of graph.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Association of Children Machines (ACM) is planning to build up a new type of puzzle for children. All the puzzles will have dimension (3×N) and has some or all of the following pieces. Some pieces can occur more than once. Since the puzzles made by ACM are in very high demand so many other companies have released counterfeit products which look just like puzzles made by ACM.

To prevent such counterfeit products ACM has taken up a measure which they hope will help the sellers to prevent the counterfeit products in their shop. As all puzzles are initially available in a box in a solved format and a (3×N) puzzle can have zillions of solutions for larger values of N. All the puzzles from ACM factory will have only some specific solutions when sold; they will be unique and only small fractions of all possible solutions. So it is more likely that the counterfeit products won’t have these orientations. You have to help them in the initial part: given the value of N you will have to find how many different solutions are there with the given pieces. You are not allowed to rotate the pieces while solving the puzzle but you can use any piece any number of time. Of course some of the pieces are mere rotation of another but they also cannot be rotated to make it look like the other. For example the piece with shape upside down T (the brown piece) cannot be rotated to look like a normal T (the pink piece).

Input

The input file contains several lines of input. Each line contains an integer N (0

Output

For each value of N produce one line of output. This line contains the serial of output followed by an integer which denotes the value (S % 1000000000000). Here S denotes the number of solutions for a (3×N) puzzle. Look at the output for sample input for details. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The rail roads of Japan are being redesigned. So the governent is planning to install ultra-modern Magnetic trains instead of the current normal trains. As fuel price have gone high and nations have shut down their nuclear plants so the price of electricity/battery is also sky high. To reduce power consumption the Japanese government is trying to descourage people from riding trains – as a result the ticket price is also kept sky high and it is strictly proportional to the square of the distance between two stations.

All the trains move in clockwise or counter clockwise order in a closed triangular track. These triangular tracks can be formed by connecting any three stations in clockwise or counterclockwise order. For simplicity you can assume that a station is denoted by a point in a two dimensional Cartesian Coordinate system. But these triangular tracks and ticket pricing policy can create new troubles. As the ticket price between two stations is proportional to the square of the distance, people often avoid the shortest route to destination and rather choose the longer one through another station. This causes more electricity expense per passenger and creates unwanted crowd in the stations. So the government would prefer not to make such tracks.

For example in the figure on the following you can see a closed triangular track marked with green. If someone wants to go from station D to station E he can go directly by riding a clockwise train or can go via station C by riding a counter clockwise train: That is he first buys ticket from station D to C and then he buys ticket of station C to E. But in the current ticket pricing system the route via C (which is also much longer) will be cheaper. So this site CED is not a place to build a track. For the similar reasons AEB is a valid site for building track. On a valid track the shortest distance between any two stations is also the unique cheapest route between them. Given the coordinate of all stations you will have to find the number of sites (a group of three places) for valid tracks.

Input

The input file contains at most 15 sets of inputs. The description of each set is given below:

Each set starts with an n (2i, y_i (0≤x_i, y_i≤10000) which denotes the Cartesian coordinate of the i-th station. You can assume that a track can be built via through any three stations, no three places will be collinear to avoid the problem of degenerate tracks and the connecting railroad between two stations can always be represented by the straight line connecting them.

Output

For each set of input produce two line of output. The first line contains the serial of output and the second line displays the total number of sites where a track can be built. Look at the output for sample input for details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Czech Technical University is rather old -- you already know that it celebrates 300 years of its existence in 2007. Some of the university buildings are old as well. And the navigation in old buildings can sometimes be a little bit tricky, because of strange long corridors that fork and join at absolutely unexpected places.

The result is that some first-graders have often diffculties finding the right way to their classes. Therefore, the Student Union has developed a computer game to help the students to practice their orientation skills. The goal of the game is to find the way out of a labyrinth. Your task is to write a verification software that solves this game.

The labyrinth is a 2-dimensional grid of squares, each square is either free or filled with a wall. Some of the free squares may contain doors or keys. There are four different types of keys and doors: blue, yellow, red, and green. Each key can open only doors of the same color.

You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls and you cannot leave the labyrinth area. If a square contains a door, you may go there only if you have stepped on a square with an appropriate key before.

Input

The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 100) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:

Note that it is allowed to have

• more than one exit,
• no exit at all,
• more doors and/or keys of the same color, and
• keys without corresponding doors and vice versa.

You may assume that the marker of your position (``*") will appear exactly once in every map. There is one blank line after each map. The input is terminated by two zeros in place of the map size.

Output

For each map, print one line containing the sentence ``Escape possible in S steps.", where S is the smallest possible number of step to reach any of the exits. If no exit can be reached, output the string ``The poor student is trapped!" instead. One step is defined as a movement between two adjacent cells. Grabbing a key or unlocking a door does not count as a step.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Envy Inc. is a joint stock company, that is, a company in which every stockholder legally owns shares of stock that account for some percentage of the total shares of stock of the company. Due to the global economic crisis, the management rules of Envy Inc. define a particular way for distributing last year's profit: if a stockholder owns more than half of the shares of stock, he/she wins the total profit. Nothing fancy so far in this wild world!

Nevertheless, there are situations in which no stockholder owns more than 50% of the shares of stock of the company. So, in order to gain some profit, stockholders are allowed to form coalitions, i.e., groups of stockholders. The participation of the coalition, share-wise, is equivalent to the sum of its stockholders' percentile participation. Hence, if a coalition has more than half of the shares of stock, its members win the totality of last years profit. Then, the members of the coalition receive a part of the profit proportional to their individual participation in the coalition.

For instance, let us assume there are 5 stockholders: A, B, C, D and E, owning 20%, 12%, 14%, 29% and 25% of the stock of the company, respectively. The stockholder E could form several winning coalitions. For example, if E were to form a coalition with A and B, he/she would get 43.86% of last year's profit. If E were to form a coalition with B and C instead, he/she would get 49.02% of last year's profit. On the other hand, E could not form a winning coalition with only A.

Your problem is, given a distribution of shares of stock of Envy Inc., and a stockholder, to determine the maximum percentage of the last year's profit that the given stockholder may win.

Input

The input consists of several test cases, each one defining a percentile distribution of shares of stock, and the index of a stockholder to determine his/her optimal participation. More precisely, each test case is defined by several input lines:

the first line contains two integer values n ( 1 <= n <= 100) and x ( 1 <= x <= n), separated by a blank, representing the number of stockholders in Envy Inc. and the index of a stockholder to determine his/her optimal participation, respectively;
each one of the following n lines has a single floating point value pi, rounded to 2 decimal places, which represents the percentage of stock ownership of stockholder i ( 1 <= i <= n). The floating point delimiter is `.' (i.e. the dot). You can assume that p1 +...+ pn = 100.

The end of the input is indicated by n = x = 0, an artificial case that must be ignored.

Output

For each given case, output a single line with the corresponding answer. The answer should be formatted and approximated to two decimal places. The floating point delimiter must be `.' (i.e. the dot). The rounding applies towards the nearest neighbor unless both neighbors are equidistant, in which case the result is rounded up (e.g. 78.312 is rounded to 78.31; 78.566 is rounded to 78.57; 78.345 is rounded to 78.35, etc.).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The poor man went to the King and said, “Lord, I cannot maintain my family. Please give me some wealth so that I can survive with my wife and children.” The King replied, “I shall grant you a piece of land so that you can cultivate and grow food for your family. In the southern part of the Kingdom there is a rectangular forest. Trees have been planted there at regular intervals. Some of the trees have been cut for use. You are allowed to take any rectangular piece of land that does not contain any tree. You need not go to the forest to select the piece of land. I have a map containing 1s at places where there is a tree and 0s at points where the tree has been cut.”



Help the poor man to find out the largest piece of land. Area of the land is measured in units of number of trees that were there. Your program should take a matrix of 1s and 0s as input and output the area of the largest rectangular piece of land that contain no tree. Be careful about the efficiency of your program.

Input

The input file may contain multiple test cases. The first line of each test case contains two integers M and N (1<=M,N<=100) giving the number of rows and columns in the matrix that follows. Each of the next M lines contains N symbols (either 0 or 1). Two consecutive symbols in a line will be separated by a single space. The input terminates with two zeros for M and N.

Output

For each test case in the input print a line giving the area (in terms of the number of trees were there) of the largest rectangular piece of land containing no tree.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the middle of Tyrrhenian Sea, there is a small volcanic island called Chronus. The island is now uninhabited but it used to be a civilized island. Some historical records imply that the island was annihilated by an eruption of a volcano about 800 years ago and that most of the people in the island were killed by pyroclastic flows caused by the volcanic activity. In 2003, a European team of archaeologists launched an excavation project in Chronus Island. Since then, the project has provided many significant historic insights. In particular the discovery made in the summer of 2008 astonished the world: the project team excavated several mechanical watches worn by the victims of the disaster. This indicates that people in Chronus Island had such a highly advanced manufacturing technology.

Shortly after the excavation of the watches, archaeologists in the team tried to identify what time of the day the disaster happened, but it was not successful due to several diffculties. First, the extraordinary heat of pyroclastic flows severely damaged the watches and took away the letters and numbers printed on them. Second, every watch has a perfect round form and one cannot tell where the top of the watch is. Lastly, though every watch has three hands, they have a completely identical look and therefore one cannot tell which is the hour, the minute, or the second (It is a mystery how the people in Chronus Island were distinguishing the three hands. Some archaeologists guess that the hands might be painted with different colors, but this is only a hypothesis, as the paint was lost by the heat). This means that we cannot decide the time indicated by a watch uniquely; there can be a number of candidates. We have to consider different rotations of the watch. Furthermore, since there are several possible interpretations of hands, we have also to consider all the permutations of hands.

You are an information archaeologist invited to the project team and are asked to induce the most plausible time interval within which the disaster happened, from the set of excavated watches.

In what follows, we express a time modulo 12 hours. We write a time by the notation hh : mm : ss , where hh , mm , and ss stand for the hour (hh = 00, 01, 02,..., 11) , the minute (mm = 00, 01, 02,..., 59) , and the second (ss = 00, 01, 02,..., 59) , respectively. The time starts from 00:00:00 and counts up every second 00:00:00, 00:00:01, 00:00:02, ... , but it reverts to 00:00:00 every 12 hours.

The watches in Chronus Island obey the following conventions of modern analog watches.


A watch has three hands, i.e. the hour hand, the minute hand, and the second hand, though they look identical as mentioned above.
Every hand ticks 6 degrees clockwise in a discrete manner. That is, no hand stays between ticks, and each hand returns to the same position every 60 ticks.
The second hand ticks every second.
The minute hand ticks every 60 seconds.
The hour hand ticks every 12 minutes.


At the time 00:00:00, all the three hands are located at the same position.

Because people in Chronus Island were reasonably keen to keep their watches correct and pyroclastic flows spread over the island quite rapidly, it can be assumed that all the watches were stopped in a short interval of time. Therefore it is highly expected that the time the disaster happened is in the shortest time interval within which all the excavated watches have at least one candidate time.

You must calculate the shortest time interval and report it to the project team.

Input

The input consists of multiple datasets, each of which is formatted as follows.


n
s1 t1 u1
s2 t2 u2
...
sn tn un


The first line contains a single integer n (2<=n<=10) , representing the number of the watches. The three numbers si , ti , ui in each line are integers such that 0 <= si, ti, ui <= 59 and they specify the positions of the three hands by the number of ticks relative to an arbitrarily chosen position.

Note that the positions of the hands of a watch can be expressed in many different ways. For example, if a watch was stopped at the time 11:55:03, the positions of hands can be expressed differently by rotating the watch arbitrarily (e.g. 59 55 3, 0 56 4, 1 57 5, etc.) and as well by permuting the hour, minute, and second hands arbitrarily (e.g. 55 59 3, 55 3 59, 3 55 59, etc.).

The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output the shortest time interval within which all the watches given in the dataset have at least one candidate time. The output must be written in a single line in the following format for each dataset.


hh:mm:ss h'h':m'm':s's'


Each line contains a pair of times hh:mm:ss and h'h':m'm':s's' , indicating that the shortest interval begins at hh:mm:ss and ends at h'h':m'm':s's' inclusive. The beginning time and the ending time are separated by a single space and each of them should consist of hour, minute, and second in two digits separated by colons. No extra characters should appear in the output.

In calculating the shortest interval, you can exploit the facts that every watch has at least one candidate time and that the shortest time interval contains 00:00:00 only if the interval starts from 00:00:00 (i.e. the shortest interval terminates before the time reverts to 00:00:00).

If there is more than one time interval that gives the shortest, output the one that first comes after 00:00:00 inclusive.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

King Motashota is in a war against the mighty Bachchaloks. He has formed a well-trained army of snipers, and planning to use them as much as possible. In one of the missions, he has S snipers. They will be dispatched to get rid of the soldiers guarding the bank of the river “Nodi'”.

From satellite images, Motashota has located positions of all enemy soldiers. Now, the plan is, snipers will take their positions. They are excellent swimmers, so, you can assume that they won't get caught, while taking position. Upon order from Motashota, they will start shooting enemy soldiers. A sniper can shoot a soldier, if euclidean distance between the soldier and sniper is no more than D. After the snipers get rid of all the soldiers, they can proceed with the operation. So, it is important for them to position the snipers in such a way that, all soldiers are within the range of at least one sniper.

In addition, when snipers start shooting, the guards will be alert, and thus, snipers can't change their position, they can only continue shooting from their position.

The river bank is defined by the horizontal line y = k. All points (x, y) where y > k is in the enemy territory, and if y < k, then it's on the water. You will be given location of N soldiers, strictly in the enemy territory, you have to place S snipers in the water, so that, they can kill all soldiers. For security reasons, the snipers should be as far from the bank as possible. For any sniper in position (x_i, y_i), the distance from the bank is |y_i - k|. If, for all snipers, the minimum of them is M = min{|y_i - k|}, you have to maximize M.

Both the soldiers and snipers are really superstitious. They will stay only in integer coordinates.

Input

First line contains an integer T (1 ≤ T ≤ 100), the number of test cases.

This is followed by T test cases. Each test case starts with four integers, k (-10⁸ ≤ k ≤ 10⁸), N (1 ≤ N ≤ 10000), S (1 ≤ S ≤ 10000) and D (1 ≤ D ≤ 10⁹), the position of the bank, number of guards and number of snipers, and the range of the snipers.

This is followed by N lines, each containing a pair of integers (x_i, y_i) the position of i^th guard (-10⁸ ≤ x_i ≤ 10⁸, k < y_i ≤ 10⁸).

There is a blank line before each test case.

Output

For each test case, output the case number followed by an integer, M, which is defined in the statement. If the snipers can’t kill all guards, output “IMPOSSIBLE”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a closed world and a set of features that are defined for all the objects in the world. Each feature can be answered with “yes” or “no”. Using those features, we can identify any object from the rest of the objects in the world. In other words, each object can be represented as a fixed-length sequence of booleans. Any object is different from other objects by at least one feature.

You would like to identify an object from others. For this purpose, you can ask a series of questions to someone who knows what the object is. Every question you can ask is about one of the features. He/she immediately answers each question with “yes” or “no” correctly. You can choose the next question after you get the answer to the previous question.

You kindly pay the answerer ¥100 as a tip for each question. Because you don't have surplus money, it is necessary to minimize the number of questions in the worst case. You don't know what is the correct answer, but fortunately know all the objects in the world. Therefore, you can plan an optimal strategy before you start questioning.

The problem you have to solve is: given a set of boolean-encoded objects, minimize the maximum number of questions by which every object in the set is identifiable.

Input

The input is a sequence of multiple datasets. Each dataset begins with a line which consists of two integers, m and n: the number of features, and the number of objects, respectively. You can assume 0 < m ≤ 11 and 0 < n ≤ 128. It is followed by n lines, each of which corresponds to an object. Each line includes a binary string of length m which represent the value (“yes” or “no”) of features. There are no two identical objects.

The end of the input is indicated by a line containing two zeros. There are at most 100 datasets.

Output

For each dataset, minimize the maximum number of questions by which every object is identifiable and output the result.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.

Input

Input consists of several test cases. The first line of input for each case contains two positive integers: n (n ≤ 15), the number of water stations, and m (m < 1000), the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord's route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

Output

For each case, there should be one line of output giving the length of Gord's jogging route.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are probably not familiar with the title, ``Gomoku", but you must have played it a lot. Gomoku is an abstract strategy board game and is also called Five in a Row, or GoBang. It is traditionally played with go pieces (black and white stones) on a go board ( 19 x 19 intersections). Nowadays, standard chessboard of Gomoku has 15 x 15 intersections. Black plays first, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five or more stones horizontally, vertically, or diagonally.

For convenience, we coordinate the chessboard as illustrated above. The left-bottom intersection is (0,0). And the bottom horizontal edge is x-axis, while the left vertical line is y-axis.

I am a fan of this game, actually. However, I have to admit that I don't have a sharp mind. So I need a computer program to help me. What I want is quite simple. Given a chess layout, I want to know whether someone can win within 3 moves, assuming both players are clever enough. Take the picture above for example. There are 31 stones on it already, 16 black ones and 15 white ones. Then we know it is white turn. The white player must place a white stone at (5,8). Otherwise, the black player will win next turn. After that, however, the white player also gets a perfect situation that no matter how his opponent moves, he will win at the 3-rd move.

So I want a program to do similar things for me. Given the number of stones and positions of them, the program should tell me whose turn it is, and what will happen within 3 moves.

Input

The input contains no more than 20 cases.

Each case contains n + 1 lines which are formatted as follows.

n
x₁ y₁ c₁
x₂ y₂ c₂
......
x_n y_n c_n

The first integer n indicates the number of all stones. n222 which means players have enough space to place stones. Then n lines follow. Each line contains three integers: x_i and y_i and c_i. x_i and y_i are coordinates of the stone, and c_i means the color of the stone. If c_i = 0 the stone is white. If c_i = 1 the stone is black. It is guaranteed that 0x_i, y_i14, and c_i = 0 or 1. No two stones are placed at the same position. It is also guaranteed that there is no five in a row already, in the given cases.

The input is ended by n = 0.

Output

For each test case:

First of all, the program should check whose turn next. Let's call the player who will move next ``Mr. Lucky". Obviously, if the number of the black stone equals to the number of white, Mr. Lucky is the black player. If the number of the black stone equals to one plus the numbers of white, Mr. Lucky is the white player. If it is not the first situation or the second, print ``Invalid."

A valid chess layout leads to four situations below:

1. Mr. Lucky wins at the 1st move. In this situation, print :

    

   
   Place TURN at (x, y) to win in 1 move.

    

   
   ``TURN" must be replaced by ``black" or ``white" according to the situation and (x, y) is the position of the move. If there are different moves to win, choose the one where x is the smallest. If there are still different moves, choose the one where y is the smallest.

2. Mr. Lucky's opponent wins at the 2nd move. In this situation, print:

    

   
   Lose in 2 moves.

3. Mr. Lucky wins at the 3rd move. If so, print:

    

   
   Place TURN at (x, y) to win in 3 moves.

    

   
   ``TURN" should replaced by ``black" or ``white", (x, y) is the position where the Mr. Lucky should place a stone at the 1st move. After he place a stone at (x, y), no matter what his opponent does, Mr. Lucky will win at the 3rd step. If there are multiple choices, do the same thing as described in situation 1.

4. Nobody wins within 3 moves. If so, print:

    

   
   Cannot win in 3 moves.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are a judge of a programming contest. You are preparing a dataset for a graph problem to seek for the cost of the minimum cost path. You've generated some random cases, but they are not interesting. You want to produce a dataset whose answer is a desired value such as the number representing this year 2010. So you will tweak (which means ‘adjust’) the cost of the minimum cost path to a given value by changing the costs of some edges. The number of changes should be made as few as possible.

A non-negative integer c and a directed graph G are given. Each edge of G is associated with a cost of a non-negative integer. Given a path from one node of G to another, we can define the cost of the path as the sum of the costs of edges constituting the path. Given a pair of nodes in G, we can associate it with a non-negative cost which is the minimum of the costs of paths connecting them.

Given a graph and a pair of nodes in it, you are asked to adjust the costs of edges so that the minimum cost path from one node to the other will be the given target cost c. You can assume that c is smaller than the cost of the minimum cost path between the given nodes in the original graph.

For example, in Figure G.1, the minimum cost of the path from node 1 to node 3 in the given graph is 6. In order to adjust this minimum cost to 2, we can change the cost of the edge from node 1 to node 3 to 2. This direct edge becomes the minimum cost path after the change.

For another example, in Figure G.2, the minimum cost of the path from node 1 to node 12 in the given graph is 4022. In order to adjust this minimum cost to 2010, we can change the cost of the edge from node 6 to node 12 and one of the six edges in the right half of the graph. There are many possibilities of edge modification, but the minimum number of modified edges is 2.

Figure G. Examples 1 and 2 of graphs

Input

The input is a sequence of datasets. Each dataset is formatted as follows.

n m c
f₁ t₁ c₁
f₂ t₂ c₂
…
f_m t_m c_m

The integers n, m and c are the number of the nodes, the number of the edges, and the target cost, respectively, each separated by a single space, where 2 ≤ n ≤ 100, 1 ≤ m ≤ 1000 and 0 ≤ c ≤ 100000.

Each node in the graph is represented by an integer 1 through n.

The following m lines represent edges: the integers f_i, t_i and c_i (1 ≤ i ≤ m) are the originating node, the destination node and the associated cost of the i-th edge, each separated by a single space. They satisfy 1 ≤ f_i, t_i ≤ n and 0 ≤ c_i ≤ 10000. You can assume that f_i ≠ t_i and (f_i, t_i) ≠ (f_j, t_j) when i ≠ j.

You can assume that, for each dataset, there is at least one path from node 1 to node n, and that the cost of the minimum cost path from node 1 to node n of the given graph is greater than c.

The end of the input is indicated by a line containing three zeros separated by single spaces.

Output

For each dataset, output a line containing the minimum number of edges whose cost(s) should be changed in order to make the cost of the minimum cost path from node 1 to node n equal to the target cost c. Costs of edges cannot be made negative. The output should not contain any other extra characters.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are a hunter chasing a monkey in the forest, trying to shoot it down with your all-powerful automatic machine gun. The monkey is hiding somewhere behind the branches of one of the trees, out of your sight. You can aim at one of the trees and shoot; your bullets are capable of going through the branches and killing the monkey instantly if it happens to be in that tree. If it isn't, the monkey takes advantage of the time it takes you to reload and takes a leap into a neighbouring tree without you noticing. It never stays in the same place after a shot. You would like to find out whether there is an strategy that allows you to capture the monkey for sure, irrespective of its initial location and subsequent jumps. If so, you need to determine the shortest sequence of shots guaranteeing this.

Figure 2

As an example, consider the situation in which there are only two neighboring trees in the forest (left hand side of Figure 2). It is then possible to make sure you capture the monkey by shooting twice at the same tree. Your first shot succeeds if the monkey happened to be there in the first place. Otherwise, the monkey was behind the other tree and it will necessarily have moved when you shoot for the second time.

However, depending on the shape of the forest it may not be possible for you to ensure victory. One example of this is if there are three trees, all connected to one another (right hand side of Figure 2). No matter where you aim at, there are always two possible locations for the monkey at any given moment. (Note that here we are concerned with the worst-case scenario where the monkey may consistently guess your next target tree).

Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing two integers n and m (1 ≤ n ≤ 21); n is the number of trees in the forest, and m is the number of adjacency relations between trees. Each of the following m lines contains two distinct integers between 0 and n - 1 (inclusive), the identifiers of the trees in an adjacent pair. The order of both trees within a pair carries no meaning, and no pair appears more than once. You may further assume that no tree is adjacent to itself, and there is always a path between any two trees in the forest.

The test cases will finish with a line containing only two zeros (also preceded with a blank line).

Output

Print a line for each test case. The line should contain the single word ‘Impossible’ if the task is impossible. Otherwise, it must contain the shortest sequence of shots with the required property, in the format L: V₁ V₂ … V_L, where L is the length of the sequence, and V₁, V₂, …, V_L are space-separated integers containing the identifiers of the trees to shoot at in the right order. If several shortest sequences exist, print the lexicographically smallest one. (A sequence is smaller than another in lexicographic order if the first element on which they differ is smaller in the first one).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Treeland Security Agency (TSA) is a secret organization supposed to maintain the security in N cities of Treeland, which are identified by the numbers from 1 to N. The city with identifier 1 is the headquarters of TSA. For the safety of all agents working for TSA, to move from one city to another city one must follow a designated two-way road system which has a tree structure rooted at the headquarters. For every mission of TSA, two secret agents located in two different cities are assigned. After completing the mission, they have to gather at a designated city, called rendezvous, and travel together to the headquarters. The rendezvous is a city which appears in both agents’ shortest routes to the headquarters and is farthest from the headquarters. This year, the director of TSA has planned K missions that will be assigned to K pairs of secret agents. He is quite interested in finding the most popular rendezvous of the year, which is the rendezvous for the largest number of missions. Given a road system among N cities and a list of cities assigned to agents in K missions, your task is to write a program to determine the most popular rendezvous.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 25. The following lines describe the data sets. For each data set, the first line contains two integers N (N ≤ 100 000) and K (K ≤ 100 000). The ith line of the following N − 1 lines contains two integers u and v (1 ≤ u, v ≤ N) separated by a space indicating that there is a two-way road between city u and v. The j-th line the next K lines contains two integers x and y (1 ≤ x, y ≤ N) separated by space describing the two cities assigned to two secret agents in the j-th mission.

Output

For each data set, write in one line the identifier of the city which is the most popular rendezvous. In case there are more than one solution, write the smallest identifier.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Tree is an important data structure. Searching is a basic operation in any data structure. In a tree searching mainly depends on its height. Consider the following three trees.

If you observe carefully, you will see that all trees are same except different nodes are used as roots. Here the height of the tree varies with the selection of the root. In the 1st tree root is '2' and height is 3. In 2nd one root is '1' and height is 2. And in last one root is '4' and height is 4. We will call '1' best root as it keeps the tree with the least possible height and '4' worst root for the opposite reason.

In this problem, you have to find out all best roots and worst roots for a given tree.

Input

Each dataset starts with a positive integer N (3 ≤ N ≤ 5000), which is the number of nodes in the tree. Each node in the tree has a unique id from 1 to N. Then successively for each i-th node there will be a positive integer K_i following id of K_i nodes which are adjacent to i. Input is terminated by EOF.

Output

For each dataset print two lines. In the 1st line show all the best roots in ascending order and in next line show all worst roots in ascending order. See sample output for exact format.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Plants versus Zombies HD Super Pro is a game played not on a grid, but on a connected graph G with no cycles (i.e., a tree). Zombies live on edges of the tree and chew through edges so that tree falls apart! Plants can be purchased and placed on vertices of the tree to protect the tree from falling apart. It is not possible to plant more than one plant on the same vertex. A plant protects one or more adjacent edges, depending on the strength and capabilities of the plant.

The Almanac offers you to buy any of three different types of plants:

• PEASHOOTERS: These are your first line of defense and can shoot peas along any one edge (of your choosing) adjacent to the vertex upon which it is placed. Cost: $100 per plant.
• SPLIT PEAS: These are hard working pea shooters and can shoot peas along any two edges (of your choosing) adjacent to the vertex upon which it is placed. Cost: $175 per plant.
• STARFRUIT: Having just visited the dentist, a STARFRUIT is very upset and shoots stars along all edges adjacent to the vertex upon which it is placed. Cost: $500 per plant.

Your goal is to protect the tree from the Zombies by having every edge covered by at least one plant, and doing so spending the least amount of money. You can buy more than one of each type of plant, but you can only plant at most one plant on each vertex.

Input

The input starts with an integer T - the number of test cases (T ≤ 100). T cases follow, each starting with the integer N on the first line, the number of vertices in G (2 ≤ N ≤ 10,000). N − 1 line follows, each containing two space separated integers u and v (0 ≤ u, v ≤ N − 1, u ≠ v) - describing an edge.

Output

For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss