Description

        Not The Huge Users Community Society (NTHUCS) is designing a new online game where people open shops to serve other people in a virtual world. In this game, each user needs to select a virtual country where he/she belongs to. Also, there is a map where each user needs to find a place to open his/her own shop (such as a restaurant, a post office, a bank, etc) to serve other people. Some parts of the map are reserved for the landscapes and the features, such as bridges, rivers, forests, remains …, etc. The remaining parts are empty spots that can be used for the shops.  There are also roads in the map, each road joining two empty spots. To increase the interaction between people from different countries, we wish to restrict that the two owners of the shops on the same road cannot be from the same country.        

        Eventually, each spot in the map will be occupied by some person. Your task is to write a program to check if there is at least a way that users can select their belonging countries so that the restriction can be followed.

Input

The first line of input contains a positive integer t (t <= 20), which indicates how many maps to check. For each map, the first line contains three positive integers n, m, k (n <= 50, m <= n*(n-1)/2, k <= n), indicating that there are n spots for opening shops (a spot is numbered from 1 to n) in the map, m roads, and people can select from one of the k countries. In next m lines, each line contains two integers u and v, which indicate the two end spots of a road.

Output

        For each map, output a line with “Yes” if this map can be used for this online game. Otherwise, output a line with “No”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.

Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.

Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?

Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format of each test case is the following:

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

Output

Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A conveyor belt has a number of vessels of different capacities each filled to brim with milk. The milk from conveyor belt is to be filled into 'm' containers. The constraints are:

 1. Whenever milk from a vessel is poured into a container, the milk in the vessel must be completely poured into that container only. That is          milk from same vessel can not be poured into different containers.
  2.The milk from the vessel must be poured into the container in order which they appear in the conveyor belt. That is, you cannot randomly          pick up a vessel from the conveyor belt and fill the container.
  3. The i-th container must be filled with milk only from those vessels that appear earlier to those that fill jth container, for all i < j

Given the number of containers 'm', you have to fill the containers with milk from all the vessels, without leaving any milk in the vessel. The containers need not necessarily have same capacity. You are given the liberty to assign any possible capacities to them. Your job is to find out the minimal possible capacity of the container which has maximal capacity. (If this sounds confusing, read down for more explanations.)

Input

A single test case consist of 2 lines. The first line specifies 1<=n<=1000 the number of vessels in the conveyor belt and then 'm' which specifies the number of containers to which, you have to transfer the milk. (1 <= m <= 1000000) .The next line contains, the capacity 1<=c<=1000000 of each vessel in order which they appear in the conveyor belt. Note that, milk is filled to the brim of any vessel. So the capacity of the vessel is equal to the amount of milk in it. There are several test cases terminated by EOF.

Output

For each test case, print the minimal possible capacity of the container with maximal capacity. That is there exists a maximal capacity of the containers, below which you can not fill the containers without increasing the number of containers. You have to find such capacity and print it on a single line.

Explanation of the output:
Here you are given 3 vessels at your disposal, for which you are free to assign the capacity. You can transfer, {1 2 3} to the first container, {4} to the second, {5} to third. Here the maximal capacity of the container is the first one which has a capacity of 6. Note that this is optimal too. That is, you can not have the maximal container, have a capacity, less than 6 and still use 3 containers only and fill the containers with all milk.

For the second one, the optimal way is, {4 78} into the first container, and {9} to the second container. So the minimal value of the maximal capacity is 82. Note that {4} to first container and {78 9} to the second is not optimal as, there exists a way to have an assignement of maximal capacity to 82, as opposed to 87 in this case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.
Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.

Input

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.

Output

For each test case, output a line containing one integer, the minimum number of dominos that must be knocked over by hand in order for all the dominos to fall.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

League of Legends(LoL) is a dota game that players should control their heroes to destory the hostile main fort.There are five players in one team ,but only three lines for hero to go.
Some heroes ,called Jungler will go to jungle which is fighting wild monsters for money and experience let the heroes on-line get more experience.Hero spends TE_i secs to fight with Monster_i and gets C_i money. If the Monster_i been killed, it would rebirth after TR_i secs. Moving between A and B should spend D_AB secs. If A, B are connected and B, C are connected, you can go to C from A in D_AB+D_BC secs.
Write a program to count the most money junger can gain in T secs(T is count from the fisrt birth time of wild monsters, all wild monsters have same fisrt birth time).
Because there are full time before the wild monster first birth, you can start from any wild monster when T=0.

Example:

Map

Monster infromation:

D₁₅ = 3,D₅₂ = 3,D₂₃ = 7,D₃₄ = 3 and T = 50;

If jungler fight wild monsters by the order 1: 1->2->3->4->5, he needs to spend TE₁ + D₁₂ + TE₂ + D₂₃ + TE₃ + D₃₄ + TE₄ +D₄₅ + TE₅ = 3+(3+3)+2+7+3+3+7+(3+7+3)+6 = 50 secs and he can gain 6+5+5+11+10 = 37.
If jungler fight wild monsters by the order 2: 1->5->2->5->1->5->2, he needs to spend TE₁ + D₁₅ + TE₅ + D₅₂ + TE₂ + D₂₅ + TE₅ +D₅₁ + TE₁ + D₁₅ + TE₅ + D₅₂ + TE₂ = 3+3+7+3+2+3+7+3+3+3+7+3+2 = 49 secs and he can gain 6+10+5+10+6+10+5 = 52. If jungler fight wild monsters by the order 2: 1->5->2->5->1->5->2, he needs to spend TE₁ + D₁₅ + TE₅ + D₅₂ + TE₂ + D₂₅ + TE₅ +D₅₁ + TE₁ + D₁₅ + TE₅ + D₅₂ + TE₂ = 3+3+7+3+2+3+7+3+3+3+7+3+2 = 49 secs and he can gain 6+10+5+10+6+10+5 = 52.
If jungler fight wild monsters by the order 3: 2->2->2->2->2->2->2->2->2->2, he needs to spend TE₂ + TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂+ TR₂ + TE₂ = 2+3+2+3+2+3+2+3+2+3+2+3+2+3+2+3+2+3+2 = 47 secs and he can gain 5*10 = 50.

We know order 2 is better than order 1 and order 3.

Input

The input consists of several test cases. Each test case begins with 3 integers in a line: The time T (1<=T<=500), the number of wild monsters N (1<=N<=50) and the number of road between wild monsters M ((N-1)<=M<=N²).

The following N lines describe the wild monsters' information. The i-th line contains three integers: the time need to fight the monster TE_i(2<=TE_i<=50) and money gain after fighting monster C_i(1<=C_i<=1000) and the rebirth time TR_i(1<=TR_i<=8) of the i-th monster.

The following M lines describe the road between wild monsters.Each line contains three integers: NO of monsterA and NO of monsterB and the moving time between A and B D_AB (3<=D_AB<=20)

Hint:

For any wild monster A,B: D_AB + TE_B + D_BA >= TR_A

Road between two wild monsters might more than one.

Output

Output the most money junger can gain in T secs.

Sample Input  Download

Sample Output  Download

Tags

Discuss