Description

ADP is a cute caterpillar living in the SK (Shik Kingdom). According to the tradition, every caterpillar in SK must go to the LAND once in the lifetime, hence ADP has just decided to make a journey. However, it's not that easy to go to the LAND, ADP will encounter birds, which will eat caterpillars, during the trip. Luckily, birds will only appear on roads between cities, so ADP can just stay in city for a while to wait for birds to fly away. ADP wrote a program to analyze the behavior of birds and find out when those birds will show up. Unfortunately, ADP is not familiar with Dijkstra
hence just can't write a program to figure out how much time this trip will takes. In order to accomplish her dream, she asks her smartest friend, you, to write the program. Can you help her?

Input

There's only one integer T in the first line, representing the number of test cases. The first line of each test case contains two integers N, M, the number of cities and the number of roads. city₀ is ADP's hometown and city_n-1 is the LAND. Each of the next M lines describes one road. There're at least four integers in each line, V1, V2, C, D, indicating that it's a bidirectional road between city_v1 , city_v2 and ADP will need C units of time to crawl through it. The next D integers T₁, T₂… TD in the line represents that birds will show up at this road at time T₁, T₂… TD. ADP will be eaten if she's still crawling on this road while birds show up. We guarantee that there's a path to get to the LAND.
1<=T<=10
1<=N, M, ΣD<=2*10^5
1<=C<=2000
0<=T_i<=2^31-1

Output

Output the minimum units of time that ADP needs to get to the LAND for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Background

   In the late XIXth century the German mathematician George Cantor argued that the set of positive fractions Q⁺ is equipotent to the set of positive integers N, meaning that they are both infinite, but of the same class. To justify this, he exhibited a mapping from N to Q⁺ that is onto. This mapping is just traversal of the N x N plane that covers all the pairs:

   The first fractions in the Cantor mapping are:

Problem

   Write a program that finds the i-th Cantor fraction following the mapping outlined above.

Input

   The inputs consists of several lines with a positive integer number i each one.

Output

   The output consists of a line per input case, that contains the i-th fraction, with numerator and denominator separed by a slash (/). The fraction should not be in the most simple form.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions . A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

Input

The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values , and .

Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an undirected weighted graph G , you should find one of spanning trees specified as follows.

The graph G is an ordered pair (V, E) , where V is a set of vertices {v₁, v₂,..., v_n} and E is a set of undirected edges {e₁, e₂,..., e_m} . Each edge e E has its weight w(e) .

A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n - 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n - 1 edges of T .

For example, a graph G in Figure 5(a) has four vertices {v₁, v₂, v₃, v₄} and five undirected edges {e₁, e₂, e₃, e₄, e₅} . The weights of the edges are w(e₁) = 3 , w(e₂) = 5 , w(e₃) = 6 , w(e₄) = 6 , w(e₅) = 7 as shown in Figure 5(b).

=6in

There are several spanning trees for G . Four of them are depicted in Figure 6(a)∼(d). The spanning tree T_a in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree T_a is 4. The slimnesses of spanning trees T_b , T_c and T_d shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree T_d in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.

Your job is to write a program that computes the smallest slimness.

Input

The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.

n m
a₁ b₁ w₁

a_m b_m w_m

Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.

n is the number of the vertices and m the number of the edges. You can assume 2n100 and 0mn(n - 1)/2 . a_k and b_k (k = 1,..., m) are positive integers less than or equal to n , which represent the two vertices v_ak and v_bk connected by the k -th edge e_k . w_k is a positive integer less than or equal to 10000, which indicates the weight of e_k . You can assume that the graph G = (V, E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).

Output

For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, `-1' should be printed. An output should not contain extra characters.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 × 10.0 × 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

Input

The input file will contain one or more test cases. On the first line of each test case there is an integer n (1 ≤ n ≤ 30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name c_i of a source currency, a real number r_ij which represents the exchange rate from c_i to c_j and a name c_j of the destination currency. Exchanges which do not appear in the table are impossible. Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input  Download

Sample Output  Download

Tags

Discuss