| . . | Without paperwork, you are a bug; with paperwork, you are a human.
-- Russian proverb |
Russia has traditionally been a very bureaucratic country, and simple paperwork often requires a lot of signatures. For example, if a Russian citizen has misplaced her internal passport, she must submit an application for a replacement, which requires signatures of four people: (1) her supervisor at work, (2) the head of the Human Resources at her work, (3) her apartment committee, which is the Russian equivalent of a landlord, and (4) the head of her local police office. Furthermore, she may need to obtain some of these signatures before others; for example, the head of the Human Resources would sign the form only after the supervisor, the apartment committee would also sign it only after the supervisor, and the police would sign it only after the apartment committee. Thus, when a Russian citizen collects the required signatures, she has to plan an appropriate order of visiting the related organizations. Your task is to write a program that helps to determine this order.
Input
The input includes multiple test cases; the number of cases is at most 20. A test case begins with a line that contains a single integer between 2 and 1,000, which is the number of constraints on the order of signatures. The following lines represent constraints, one per line; each constraint consists of two words, separated by a single space, which represent signatures. The first signature in a constraint must be obtained before the second; for example, the constraint "supervisor police" means that the supervisor must sign the form before the police. The input includes at least one constraint for each required signature, which means that the constraint list includes all signatures. The words that represent signatures are strings of lower-case letters, which include from one to twenty letters. The last line of the input, after the last test case, is "0".
Output
For each test case, the output is a valid ordering of the signatures, where each signature is on a separate line. If the constraints allow several orderings, the output may include any of these orderings. If the constraints do not allow any valid ordering, the output is "no valid ordering". The output should include a blank line in the end of each test case, which separates it from the next case.
Sample Input
4 supervisor humanresources supervisor landlord supervisor police landlord police 4 supervisor humanresources humanresources landlord landlord supervisor landlord police 0Sample Output
supervisor humanresources landlord police no valid ordering
| . . | Tea is not vodka, you cannot drink a lot of it.
-- Russian proverb |
The Russian people are famous not only for their writers, scientists, and chess players, but also for their ability to consume large quantities of alcohol. When Russians get tired of drinking vodka by itself, they mix it with other beverages; in particular, the Russian tea is a drink based on the mixture of vodka and tea. To make this drink, a Russian takes a cup of tea and a bottle of vodka. He drinks a milliliter of tea, adds a milliliter of vodka to the tea, and mixes the resulting drink, so that vodka is uniformly distributed in the tea. He then drinks a milliliter of the resulting mix, adds another milliliter of vodka, and mixes it again. He repeats this "drink and add vodka" step until he runs out of vodka. Your task is to determine the concentration of tea in the final mix.
Input
The input includes multiple test cases, each on a separate line; the number of cases is at most 2,006. Each test case includes two positive integers on the same line, separated by a single space, with no spaces before the first integer or after the second. The first integer is the initial volume of the tea, and the second is the initial volume of the vodka; both values are in milliliters, and they both are between 1 and 100,000,000. The last line of the input is "0 0", which does not represent a test case.
Output
For each test case, the output is the concentration of tea in the mix at the end of drinking, which is between 0.000 and 1.000. You should round this concentration to three decimal places, and you should output the answer for each test case on a separate line.
Sample Input
10 1 10 10 100 100 1000 10000 0 0Sample Output
0.900 0.349 0.366 0.000
| . . | There is no such thing as too much vodka.
-- Russian proverb |
When you drink a cup of Russian tea, you get a taste of the Russian culture, but it does not make you Russian; to become a true part of the culture, you should drink a lot of it. If you are not yet ready for this experience, you can start by writing its computer simulation; that is, you should solve the Russian Tea problem for very large quantities of tea and vodka.
Input
The input includes multiple test cases, each on a separate line; the number of cases is at most 2,006. Each test case includes two positive integers on the same line, separated by a single space, with no spaces before the first integer or after the second. The first integer is the initial volume of the tea, and the second is the initial volume of the vodka; both values are in milliliters, and they both are between 108 and 10100. Note that these values may be greater than standard integers in C++ and Java. The last line of the input is "0 0", which does not represent a test case.
Output
For each test case, the output is the concentration of tea in the mix at the end of drinking, which is between 0.000 and 1.000; it should be rounded to three decimal places.
Sample Input
100000000 10000000000 10000000000 100000000 10000000000 10000000000 100000000000000000000 100000000000000000000 0 0Sample Output
0.990 0.000 0.368 0.368