Description

Ordering

Background

Order is an important concept in mathematics and in computer science. For example, Zorns Lemma states: a partially ordered set in which every chain has an upper bound contains a maximal element. Order is also important in reasoning about the fix-point semantics of programs.
This problem involves neither Zorns Lemma nor fix-point semantics, but does involve order.

Problem

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of two lines: a list of variables on one line, followed by a list of constraints of the form A < B on the next line. Variables and contraints are separated by single spaces.
All variables are single character, upper-case letters. There will be at least two variables, and no more than 20 variables. There will be at least one constraint, and no more than 50 constraints. There will be no more than 300 orderings consistent with the contraints in a specification.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

All orderings consistent with the constraints should be printed. Orderings are printed in alphabetical order, one per line. Characters on a line are separated by a space. If no ordering is possible, the output is a single line with the word NO.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Sultan of Nubia has no children, so she has decided that the country will be split into up to k separate parts on her death and each part will be inherited by whoever performs best at some test. It is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains and the delicate scent of incense have been placed k chessboards. Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one.)

Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.)

Input

Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a positive integer less than 100. There will never be more than 20 boards.

Output

Output will consist of k numbers consisting of your k scores, each score on a line by itself and right justified in a field 5 characters wide.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

These days, you can do all sorts of things online. For example, you can use various websites to make virtual friends. For some people, growing their social network (their friends, their friends' friends, their friends' friends' friends, and so on), has become an addictive hobby. Just as some people collect stamps, other people collect virtual friends.

Your task is to observe the interactions on such a website and keep track of the size of each person's network.

Assume that every friendship is mutual. If Fred is Barney's friend, then Barney is also Fred's friend.

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 an integer F, the number of friendships formed, which is no more than 100 000. Each of the following F lines contains the names of two people who have just become friends, separated by a space. A name is a string of 1 to 20 letters (uppercase or lowercase).

Output

Whenever a friendship is formed, print a line containing one integer, the number of people in the social network of the two people who have just become friends.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recently, Mr. ATH's hard disk is almost full so his computer crashes often. He decided to clean up his hard disk by
uninstalling some programs. Currently his computer is running under an operation system called SOD, which is an
operation system that has similar commands to DOS.

To remove a program, he needs to change his working directory to the directory of the program.
After typing "uninstall" in the directory, then the program will be automatically uninstalled.

However, unlike DOS, this operation system's command of changing directory is fairly limited.
The command "cd" has the following usage:

1. cd [directory_name]
   This command would allow user to swap his directory exactly one level down in the hierarchy.
   For example, if the current directory is "/tmp", the command "cd aaaa" would change the directory to "/tmp/aaaa"
   However, "cd aaaa/bbbb" does not work.
    
2. cd ..
   This command would allow user to move his directory one level up in the hierarchy.
   For example, if the current directory is "/tmp/aaaaa", the command "cd .." would change the directory to "/tmp"

Note that in the SOD operation system, the root directory is "/" and he started at root directory initially.

Now Mr. ATH has listed the directories of the programs that he wanted to delete IN ORDER,
because violation of the order would cause his computer to crash.

Since the function of executing a batch file is not even implemented in SOD operation system (what a bad OS),
Mr. ATH would have to type these commands by hand.
Besides, because Mr. ATH is lazy, he wanted to type as few lines of commands as possible.

You going to write a program that will generate minimum lines of commands that Mr. ATH could use to
delete all program he listed.

Input

The input may contain many cases (Mr. ATH need to clean his hard disk very often).
The first line of each case contain exactly one integer n (1<=n<=50) indicating the number of program that Mr. ATH wanted to delete.
Then the following n lines consist of strings without any spaces that describe the directories of the programs.
The names of adjacent directories are separated by a slash "/", and there is no slash succeeding the last directory name.
There will be no same strings appear in the same case. Besides, he will not uninstall his root directory "/".

The name for each directory has length at least 1 and at most 32 and consist of
only letters (a-z, A-Z), digits (0-9) and underscores "_".
Moreover, the SOD operation system can only allow the depth of hierarchy to at most 10 levels.
That is, "/1/2/3/4/5/6/7/8/9/10" is valid, while "/1/2/3/4/5/6/7/8/9/10/11" is not a valid directory.
You should also note that the names are case sensitive, that is, "/Aaaa" is a directory different from "/aaaa".

Output

For each case, output "Case x:" in the first line, where x is the number of case, starting from 1.
Then output the commands, each in a line, which can be "cd ..", "cd [directory_name]", or "uninstall".
Note that he always starts at root directory "/" in every case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Sometimes, if you are searching for ladybugs, all you find are tree fleas. An old tree near the anthill serves as a home of two fleas who sometimes steal honeydew from aphids living on the tree. On the old tree, branches connect the forks (spaces where two or more branches meet) and leaves where the fleas can rest. Fleas are so small that the ants cannot see them and thus fleas are safe. Because of their size, the fleas satiate their appetite pretty quickly and then have a lot of energy to jump. They decide to jump toward each other complying with the following rules:

There is exactly one way for the fleas to go from one leaf or fork in the tree to another leaf or fork without ever turning back. Each of the fleas starts jumping along such a route to the current location of the other flea.
The fleas can only jump from one fork or leaf of the tree to another fork or leaf if they are connected by a branch.
If the two fleas land at the same time in the same place then they decide to sit and chat for quite a while.
If the two fleas land at the same time in two neighboring places on the tree (forks or leaves) then they keep jumping forever.
The input file contains multiple test cases. Each test case starts with an integer n, the number of leaves and forks in the tree, 1≤n≤5000. We assume that leaves and forks are numbered from 1 to n. Each of the following n-1 lines describe tree branches; each branch is described by two integers a and b, meaning that the branch connects the fork or leaf labeled a and the fork or leaf labeled b. In the (n+1)-st line there is one integer l, 1≤l≤500, saying how many starting positions of the fleas you are to consider for the tree. Each of the following l lines contains two positive integers (not greater than n). These numbers define the tree places in which the fleas start their jumping. Input is terminated by the case with n equal to 0.
Your program should output l lines for each test case. The i-th line for a case should look like

The fleas meet at p.

where p identifies the place where the fleas meet, or

The fleas jump forever between p and r.

where p and r are two neighboring places on the tree with p ≤ r

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss