Description

Given a simple, undirected weighted graph G = (V, E, W), output the weight of its minimum spanning tree.

Input

The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node N and the number of the edges M. In the following M lines, each line contains three integers (s_i, e_i, c_i), 1 <= s_i, e_i <= N, 1 <= c_i <= 100, representing the indices of end vertices of an edge and the weight of the edge.

Case 1: 2 <= N <= 10², 1 <= M <= 10³
Case 2: 2 <= N <= 10³, 1 <= M <= 10³
Case 3: 2 <= N <= 10³, 1 <= M <= 10⁴
Case 4: 2 <= N <= 10³, 1 <= M <= 10⁵

Output

For each case, output a single line that indicates the weight of the minimum spanning tree of the graph.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a number sequence S = {S1, S2, S3, …, Sn}, we called (i,j) an “inversion pair” when Si > Sj and i < j. Given S, calculate the number of inversion pair in this sequence.

Case1: 1<=N<=10^2
Case2: 1<=N<=10^3
Case3: 1<=N<=10^5
Case4: 1<=N<=10^6

Input

There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 10^6) in a line, and then N integers(each number fits in 64-bit integer) follow, in a single line. The input is terminated by the number zero.

Output

For each test case, print a number of inversion pairs in the given sequence. All the answer can be fit in 64-bits integers.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You need to write a program to simulate a queue of names.  Each name is a string consisting of English letters only.  There are three operations:

1.         “Push [name]”, which means to enque name in the queue.

2.         “Pop”, which means to deque. If the queue is empty, this operation takes no effect.

3.         “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).

Case1 : #operation <= 10^2, There will be no "Pop" and "Front" command when queue is empty.
Case2 : #operation <= 10^3. There will be no "Pop" and "Front" command when queue is empty.
Case3 : #operation <= 10^4.
Case4 : #operation <= 10^6.

Input

Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.

Output

For each “Front” operation, print out the name in the front of the queue.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

Case 1 : N≤50

Case 2: N≤100

Case 3: N≤1000

Case 4: N≤10000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence S of digits and a number k, for example S = “4113” and k = 2.
In the sequence S, there is one 4, followed by two 1, followed by one 3. 
Then we can produce a new sequence S’ = 142113.
(note : 
“one 4” -> 14
“two 1” -> 21
“one 3” -> 13
)

This is the first round, and we need to do it for k rounds.

The input of i round is the output from i-1 round. (i>1)
When i = 1, the input is sequence S, we will give you.

Now, we want you to print the output after k rounds.

Another example : 

S = "323", and k = 1

then we have one 3,followed one 2, and followed one 3

so S' would be "131213"

(note:

"one 3" -> 13

"one 2" -> 12

"one 3" -> 13

)

Input

The input includes multiple test cases. 
The first of the input is an integer T (T <= 1000) specifying the number of test cases. 
For each case, the first line contains the sequence S.
The second line contains one integer k.

limits 
Case 1 : length of S <= 5, 1<=k<=2
Case 2 : length of S <= 100, 1<=k<=2
Case 3 : length of S <= 1000, 1<=k<=10
Case 4 : length of S <= 1000, 1<=k<=10

Output

For each test case outputs one line, the output after k rounds.  

Sample Input  Download

Sample Output  Download

Tags

Discuss