- Input file:
**a.in** - Output file:
**a.out** - Time Limit:
**6 sec** - Memory Limit:
**64 Mb**

A group of AntiGlobalists has decided to move to a new village on the boundary of a huge forest.

The arrangement of houses and paths in the village turned out to be a
major problem: Many of the AntiGlobalists are friends and want to visit each
other often, so they want to have a path between their houses. However the
AntiGlobalists are also known for quarreling with everyone else. To avoid the
chance of meeting with someone they do not like, it is required that no
two paths intersect - there should be no crossroads in the village (*And
of course also no other means of crossing; overpasses spoil the scenery
and underpasses destroy the root systems of precious herbs.*) . Each
AntiGlobalist also wants to be able to visit the forest, of course without
having to cross any path - i.e., it is also necessary to make it possible
to get from each house to ``infinity'' without crossing a path.

You are given a description of the relationships between AntiGlobalists. Your task is to decide whether such an ideal village can be built.

The input consists of several instances.

The first line of each instance contains two integers 1 *H*
10 000 and *F* 0 separated
by a single space. *H* is the number of AntiGlobalists. The AntiGlobalists
have assigned integers between 0 and *H* - 1. *F* is the number
pairs of friends. The following *F* lines of the instance describe
the pairs of friends. Each of the lines contains two integers 0
*h*_{1}, *h*_{2} < *H* separated by a
single space, meaning that AntiGlobalists with numbers *h*_{1}
and *h*_{2} are friends. Each pair of friends is described
exactly once.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

The output consists of several lines. The *i*-th line of the
output corresponds to the *i*-th instance. If it is possible to build
a village for the corresponding input instance, the output line consists
of ``Yes, village can be built'' string. If it is not possible to build
such a village, the output line consists of ``No, village cannot be
built'' string.

3 3 0 1 0 2 1 2 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 0

Yes, village can be built No, village cannot be built

- Input file:
**b.in** - Output file:
**b.out** - Time Limit:
**2 sec** - Memory Limit:
**64 Mb**

Boatherds Inc. is a sailing company operating in the country of Trabantustan and offering boat trips on Trabantian rivers. All the rivers originate somewhere in the mountains and on their way down to the lowlands they gradually join and finally the single resulting river flows to the sea. Moreover, the Trabantian villages are exactly at the rivers' springs, junctions and at the mouth of the largest river. Please note that more than 2 rivers can join at a junction. However, the rivers always form a tree (with villages as vertices).

The pricing policy of the Boatherds is very simple: each segment of each river between two villages is assigned a price (the price is same in both directions), so if a tourist requests a journey between any two villages, the ticket office clerks just add the prices of the segments along the only path between the villages.

One day, a very strange tourist appeared. She told the clerks that she returns to her country on the next day and she wants to spend all the remaining money on a boat trip, so they should find a route with exactly this cost. Being just poor (ahem) businessmen, they have asked the Abacus Calculator Makers for help.

You are given a description of the river network with costs of river
segments and a sequence of integers *x*_{1},...,
*x*_{k}. For each *x*_{i}, you should determine
if there is a pair of cities (*a*, *b*) in the river network
such that the cost of the trip between *a* and *b* is exactly
*x*_{i}.

The input consists of several instances. Each instance is described by (in the following order):

- A single line containing a single integer: the number of villages
*N*(1*N*10 000). *N*lines describing the villages. The*i*-th of these lines (1*i**N*) describes the village with number*i*. It contains space separated integers*d*_{1},*c*_{1},*d*_{2},*c*_{2}, ,*d*_{ki},*c*_{ki}, 0. The*d*_{j}'s are numbers of villages from which the rivers flow directly to the village*i*(with no other villages in between), each*c*_{j}is the price of the journey between villages*i*and*d*_{j}. Moreover, 2*d*_{j}*N*and 0*c*_{j}1 000. Village 1 always corresponds to the mouth of the largest river, therefore no*d*_{i}can ever be equal to 1.*M*100 lines describing the queries. The*i*-th of these lines corresponds to the*i*-th query and contains a single integer*x*_{i}(1*x*_{i}10 000 000).- The instance is finished by a single line containing the number 0.

The whole input is ended by a single line containing the number 0.

For each instance you should produce a sequence of *M* lines
(where *M* is the number of queries in the particular instance). The
*i*-th of these lines contains the word ``AYE'' if there exists a
pair of cities in the river network which is connected by a path of cost
*x*_{i}, or the word ``NAY'' otherwise.

Output for each instance must be followed by a single line containing just the dot character.

6 2 5 3 7 4 1 0 0 5 2 6 3 0 0 0 0 1 8 13 14 0 0

AYE AYE NAY AYE .

- Input file:
**c.in** - Output file:
**c.out** - Time Limit:
**2 sec** - Memory Limit:
**64 Mb**

A Compiler Mystery: We are given a C-language style `for` loop
of type

for (variable = A; variable != B; variable += C) statement;

I.e., a loop which starts by setting *variable* to
value *A* and while *variable* is not equal
to *B*, repeats *statement* followed by increasing the
*variable* by *C*. We want to know how many times does
the *statement* get executed for particular values of *A*,
*B* and *C*, assuming that all arithmetics is calculated in a
*k*-bit unsigned integer type (with values 0 *x* <
2^{k}) modulo 2^{k}.

The input consists of several instances. Each instance is described by
a single line with four integers *A*, *B*, *C*, *k*
separated by a single space. The integer *k* (1 *k* 32)
is the number of bits of the control variable of the loop and *A*,
*B*, *C* (0 *A*,
*B*, *C* < 2^{k}) are the parameters of the loop.

The input is finished by a line containing four zeros.

The output consists of several lines corresponding to the instances on
the input. The *i*-th line contains either the number of executions
of the *statement* in the *i*-th instance (a single integer
number) or the word `FOREVER` if the loop does not terminate.

3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0

0 2 32766 FOREVER

- Input file:
**d.in** - Output file:
**d.out** - Time Limit:
**7 sec** - Memory Limit:
**64 Mb**

A not very famous writer Arthur Conan Moyle has finally found out why his books are not as popular as he believes they would deserve. He noticed that his works are getting a bit boring due to frequent repetitions of same or similar pieces of text. He decided that the best way how to improve the quality of his books is to simply throw away everything after the first repetition - the books then get an interesting open-ended feeling.

First he attempted to look for exactly same pieces of text, but this
failed, since the repeated texts often do not match precisely - some of
letters that are lowercase in the first place may be uppercase in the
second and vice versa, punctuation may be a bit different, and even the
words in sentences may be in slightly different order. To overcome these
problems, he devised the following more involved criterion for recognizing
duplicates (a positive integer *k* is a parameter of his criterion;
by changing it he affects how long repeated pieces are still acceptable):

Alphabetic characters are the letters 'a'-'z' and 'A'-'Z'. We do not distinguish case of the letters, i.e. 'a' is supposed to be the same letter as 'A'.

Two strings *S*_{1} and *S*_{2} are
* k-identical up to permutation of letters* if:

- Both
*S*_{1}and*S*_{2}start and end with an alphabetic character - Both
*S*_{1}and*S*_{2}contain exactly*k*alphabetic characters - For each alphabetic character
*c*, the string*S*_{1}contains the same number of occurrences of*c*as the string*S*_{2}.

In other words, if the strings *S*_{1} and
*S*_{2} are *k*-identical up to permutation of letters,
then the alphabetic characters in them are the same, but their ordering
may be different.

Your task is to write a program that separates a longest initial part
that does not contain two substrings *k*-identical up to permutation
of letters from several of the ACM's books.

The input consists of several instances. Each instance is described by two lines.

The first line of the instance consists of an integer number 1
*k* 50. The
second line of the instance consists of the string *T*. Length of
*T* is at most 100 000 characters. The string *T* may
contain non-alphabetic characters including spaces, but it does not
contain any characters with special meaning (i.e. with ASCII code smaller
than 32).

The input is terminated by a line containing a zero.

The output consists of several lines. The *i*-th line of the
output corresponds to the *i*-th input instance. The line a single
integer number - length of the longest prefix *P* (including all
non-alphabetic characters) of the string *T* of the corresponding
instance such that *P* does not contain two distinct, but not
necessarily non-overlapping, substrings *S*_{1} and
*S*_{2} that are *k*-identical up to permutation of
letters.

4 a'B'C'd'x'a'b'c'd 4 abcdabcd 0

16 4

- Input file:
**e.in** - Output file:
**e.out** - Time Limit:
**7 sec** - Memory Limit:
**64 Mb**

Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country.

ACM++ has therefore decided to connect the networks of some of the plants together. At least in the first stage, there is no need to connect all plants to a single network, but on the other hand it may pay up to create redundant connections on critical places - i.e. the network may contain cycles. Various plans for the connections were proposed, and the complicated phase of evaluation of them has begun.

One of the criteria that has to be taken into account is the reliability of the created network. To evaluate it, we assume that the worst event that can happen is a malfunction in one of the joining points at the power plants, which might cause the network to split into several parts. While each of these parts could still work, each of them would have to cope with the problems, so it is essential to minimize the number of parts into which the network will split due to removal of one of the joining points.

Your task is to write a software that would help evaluating this risk. Your program is given a description of the network, and it should determine the maximum number of non-connected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself).

The input consists of several instances.

The first line of each instance contains two integers 1 *P*
10 000 and *C* 0 separated
by a single space. *P* is the number of power plants. The power
plants have assigned integers between 0 and *P* - 1. *C* is the
number of connections. The following *C* lines of the instance
describe the connections. Each of the lines contains two integers 0
*p*_{1}, *p*_{2} < *P* separated by a
single space, meaning that plants with numbers *p*_{1} and
*p*_{2} are connected. Each connection is described exactly
once and there is at most one connection between every two plants.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

The output consists of several lines. The *i*-th line of the
output corresponds to the *i*-th input instance. Each line of the
output consists of a single integer *C*. *C* is the maximum
number of the connected parts of the network that can be obtained by
removing one of the joining points at power plants in the instance.

3 3 0 1 0 2 2 1 4 2 0 1 2 3 3 1 1 0 0 0

1 2 2

- Input file:
**f.in** - Output file:
**f.out** - Time Limit:
**9 sec** - Memory Limit:
**64 Mb**

The Association for Courtly Manners, an international organization for
standardization of social interactions (*Better known under the name
Absurdly Clumsy Moralists, but let's not take prejudice.*) has decided
to create a new international standard defining ranks of firepersons
(*Formerly firemen, but the international standards of course must be
politically correct.*) - each fireperson receives an integer number
describing his rank and when they arrive to a fire, they must enter the
fire ground in order of increasing ranks and the low ranked firepersons
must keep the fire burning long enough for the high ranked firepersons to
enjoy extinguishing sufficiently.

The ranks are assigned according to an Arbitrary Constant Multiplier
Sequence. An ACM-sequence of order *k* is an integer sequence defined
by its first *k* terms *a*_{0},
*a*_{1},...*a*_{k-1} and a recurrence relation
mod 10 000 for *n* *k*,
where the *b*_{i}'s are integer constants. The *i*-th
oldest fireperson then gets rank *a*_{i}.

Your task is to calculate the rank of the *i*-th fireperson, given
parameters of the ACM-sequence and the number *i*.

The input consists of several instances. Each instance is described on
a single line containing the following integers separated by a single
space: *k*, *a*_{0}, , *a*_{k-1},
*b*_{1}, , *b*_{k}, *i*. Here 1
*k* 100 is the
order of the sequence, 0
*a*_{i} < 10 000 are the first *k* elements of
the sequence, 0
*b*_{i} < 10 000 are the multipliers and 0
*i* < 1 000 000 000 is the number of the element we
ask for.

The input ends with a line containing a number 0.

The output consists of several lines corresponding to the instances on
the input. The *l*-th line contains a single integer
*a*_{i} which is the *i*-th element of the sequence
described by the *l*-th input instance.

2 0 1 1 1 6 0

8