Description

Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order.  Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases.  Each test case begins with an integer N, denoting the number of relations in the tree.  In the following N lines, each line contains two integers a and b, which means node a is node b’s parent.   After that, the next line contains an integer R, which represents the root of the tree.  You can assume that all the nodes will be on the same tree.  The input is terminated by N = 0.

Case 1: 1 <= N <=10 , 1 <= a,b <= 20

Case 2: 1 <= N <=100 , 1 <= a,b <= 200

Case 3: 1 <= N <=1000 , 1 <= a,b <= 2000

Case 4: 1 <= N <=1000 , 1 <= a,b <= 2000000

Output

For each test case, print the pre-order of the tree.  In each level, traverse the node with smaller ID first.

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).

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.

Case 1: 0 < #operations <= 10^4

Case 2: 0 < #operations <= 10^5

Case 3: 0 < #operations <= 10^6

Case 4: 0 < #operations <= 10^7

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We can encrypt a string into other string.  One method is to put a string into an n×n array first, where n is the smallest number such that n2 is equal to or larger than the length of the string.  Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order.  The encrypted string is the output of the row major order.  For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.

The output string is "Googrd  e  sed i".

If the end of the encrypted string are spaces, don't output them.  For example, the output of "Bass GG" is "B Ga Gss".

Input

The input consists of multiple lines.  Each line is a test case, a string S with length <= 1000.  The number of test case is less than 100.

Output

For each test case, output the encrypted string of S.

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 ≤ 1000) 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).

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

Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either 

(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or 
(iii) pop from the stack, and output that number.

Can we obtain the output sequence as 1, 2, 3, ..., n.

So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.

Hint: 
Our strategy could be as follows. 
First, we try operation (iii). 
If it is invalid, then we try operation (i). 
If it cannot produce what we want, try operation (ii). 
If we run out of the supply and the stack is not empty. The answer is NO.

Input

There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).

Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000

Output

For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".

Sample Input  Download

Sample Output  Download

Tags

Discuss