Sociologists are interested in the phenomenon of "friendship". To study this property, they analyze various groups of people. For each two persons in such a group they determine whether they are friends (it is assumed that this relation is symmetric). The sociologists are mostly interested in the sets of friends. The set S of people is the set of friends if every two persons in S are friends. However, studying the sets of friends turns out to be quite complicated, since there are too many such sets. Therefore, they concentrate just on the maximal sets of friends. A set of friends S is maximal if every person that does not belong to S is not a friend with someone in S.
Your task is to determine the number of maximal sets of friends in each group. In case this number exceeds 1 000, you just need to report this -- such a group is too complicated to study.
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers 1 n 128 and m -- number of persons in the group and number of friendship relations. Each of m following lines consists of two integers ai and bi (1 ai, bi n). This means that persons ai and bi (ai bi) are friends. Each such relationship is described at most once.
The output for each instance consists of a single line containing the number of maximal sets of friends in the described group, or string "Too many maximal sets of friends." in case this number is greater than 1 000.
5 4 1 2 3 4 2 3 4 5
4
Alice and Bob started to play the following game: they have an m×n chessboard, with some of the fields removed. There are two chess pieces on distinct (non-removed) fields of the board. Alice always makes the first move and then she alternates with Bob in turns. Each turn consists of moving one of the pieces by one field horizontally or vertically. Both players can move any of the pieces, regardless of the piece moved in the previous turn. The piece cannot be moved to a removed field. The player that is able to move one of the pieces to the field occupied by the other one, thus capturing it, wins.
After some time, they found the game very boring -- nobody could win, and the pieces just chased each other around the board. Therefore, they introduced a new rule -- no player may move a piece in such a way that a position that already appeared during the game is repeated. The position is considered to be the same if the fields occupied by the pieces are the same (the pieces cannot be distinguished), regardless of who is on turn in the particular position. Additionally, they introduced a rule that the player who cannot make a legal move loses. Now the game is always finite and one of the players will surely win. Your goal is to find a winning strategy, if one exists.
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers m and n, 1 m, n 8. Each of m following lines consists of n characters and determines the initial state of the chessboard. The characters are one of the following:
There are always precisely two characters "P" in each instance.
The output for each instance consists of a single line containing either the string "Alice wins." if Alice has a winning strategy in the described position, or the string "Bob wins.", if she has no such strategy.
4 4 P.## ..## ##.. ##.P 1 5 P...P
Alice wins. Bob wins.
ACM has bought a new crane. The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 i < n. The beginning of the first segment is fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen.
Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180o. The operator issues commands that change the angle in exactly one joint.
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers 1 n 10 000 and c 0 separated by a single space -- the number of segments of the crane and the number of commands. The second line consists of n integers l1,..., ln (1 li 100) separated by single spaces. The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 s < n, 0 a 359) separated by a single space -- the order to change the angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).
The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space -- the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point. The output is judged to be correct if each of the coordinates differs by at most 0.02 from the correct position of the end of the crane.
The outputs for each two consecutive instances must be separated by a single empty line.
2 1 10 5 1 90 3 2 5 5 5 1 270 2 90
5.00 10.00 -10.00 5.00 -5.00 10.00
There are n towns in the kingdom of Failland. In the past, Failland used to have an excellent system of roads, connecting each town directly to each other, without any two roads crossing -- they used a complicated system of bridges to ensure this. Recently, however, the Road-workers Union split into n independent divisions, one for each town. Due to a huge aversion between divisions, each division strictly refuses to maintain roads that lead to a town controlled by any other division. Since initially each division controlled one town only, all of the roads were soon completely broken.
The wise king of Failland has decided to improve the situation using decrees. In several decrees, he ordered some of the divisions to unite again. Whenever road-workers received such a decree, they obeyed (Well, wouldn't you obey the order when the only other option was to have your head chopped off?) and the divisions in concern were immediately united into a single one. But since the workers are lazy and the decree did not explicitely say otherwise, the union process did not affect the roads being maintained. The united division still maintained only those roads that it used to maintain before.
Therefore, the king started to issue another type of decrees, saying that the road workers of some division must immediately repair all of the destroyed roads between the towns the division controls. He then repeated the whole process of uniting the divisions and ordering them to work several times, and finally, when only one united division remained, he considered the problem solved and went for a vacation.
However, citizens of Failland soon noticed that there is still something wrong, and that there are too few roads. After some research, they found out that whenever the workers of a division accepted an order to repair all of the destroyed roads, they also automatically supposed that they can stop maintaing the roads they maintained before, and such roads decayed quickly.
In order to persuade the king to return from the vacation and to solve the problem somehow, citizens have decided to find as many towns as possible such that no two of them are connected by a direct repaired road. They plan to send this list to the king because they feel it could help somehow. However, this task turned out to be too difficult, thus they decided to ask you for help.
The input consists of several scenarios. Each scenario consists of a single line. This line contains an expression that describes the sequence of king's decrees, and hence also the current state of the roads in Failland. The expression is one of the following:
For example, "C U U V V V" describes the land with three towns controlled by a single union, and with all three roads between these towns in a perfect condition, forming a triangle. The expression "U C U U V V V C U U V V V" describes the land with six towns formed as a union of two such triangles. The expression "C U C U U V V V C U U V V V" describes the same land after the decree that orders road-workers to repair the neglected roads. Now the land has six towns and 9 roads -- all of the roads between all pairs of towns, except for those six that belonged to the triangles.
Each line of the input contains at most 200 000 characters.
The output for each scenario consists of a single line containing a single integer -- the maximum number of towns such that no two of them are connected by a maintained road.
U V V U C U V V V C U C U U V V V C U U V V V
2 2 3
Go is an oriental board game. The goal in this game is to surround as much territory as possible by stones of your color. This game is very difficult to play for computers -- the best available programs are beaten easily by a human with just a few months of practice. Some parts of the game however can be managed easily under some assumptions. This task is about the endgame stage of the go match, when boarders of all the territories are almost completely finished and the players try to squeeze last few points. Even this stage of the game is very difficult, thus we only concentrate on much simplified model. As usual, the game is played by Alice and Bob, and the alternate on the move.
We assume that Alice has a points of territory and Bob has b points. There are n separated regions such that moves in each of the regions do not affect the moves in other regions. Suppose it is Alice's turn. The endgame proceeds as follows: Alice chooses a region and plays there. Bob responds to this move in the same region, then Alice responds to the Bob's move, and so on, until a settled state is reached. The player who is on turn then chooses another region and plays there, and the game proceeds in the same way until all regions are settled.
The player who starts to play in a region has an advantage and usually gains more points there than the other player. To model this, for the i-th region we know that if Alice starts playing there, she gains ai points and Bob gains nothing, while if Bob starts playing there, he gains bi points and Alice gains nothing.
Additionally, playing in this region may be sente for Alice or Bob. If region is sente for the player who starts playing there, he will be on turn after the region is settled, and thus he is the one to choose the next region to play in. If the region is not sente for the player who starts playing there, the other player is on turn when the region is settled. The region may be sente for both players, for only one of them, or for nobody.
Your task is, given the description of the regions, to determine the final score of the game, assuming that both players use the optimal strategy. Each player tries to have the score greater than the score of the other player by as much as possible (or smaller by as little as possible), and among the results with the same difference of scores, they prefer the one where they have the maximal score.
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of three integers a, b (0 a, b and a + b 361) and n (0 n 361) separated by single spaces -- the current numbers of points of Alice and Bob, and the number of unresolved regions. Each of the following n lines describes a single region. The line describing the i-th region consists of two integers ai and bi (0 ai, bi and 1 ai + bi 361), and two characters si and ti, separated by single spaces. The integers ai and bi are the numbers of points gained by Alice and Bob by starting to play in each region. The character si is "S" if the region is sente for Alice, and "G" otherwise. Similarly, ti is "S" or "G", depending on whether the region is sente for Bob or not.
The output for each instance consists of a single line containing two integers A and B separated by a single space. These integers are the final number of points of Alice and Bob, assuming that they both play out the rest of the game using the optimal strategy, and Alice is on turn in the beginning. For all input instances, A + B 361.
0 0 1 5 6 G S 10 9 3 2 10 G G 1 1 S G 8 6 G S
5 0 19 19
Roman numerals are represented by a string consisting of characters "I", "V", "X", "L", "C", "D" and "M". These symbols represent the decimal values 1, 5, 10, 50, 100, 500 and 1000, respectively. To represent other values, these symbols, and multiples where necessary, are concatenated, with the smaller-valued symbols written further to the right. For example, the number 3 is represented as "III", and the value 73 is represented as "LXXIII". The exceptions to this rule occur for numbers having units values of 4 or 9, tens values of 40 or 90, and hundreds values of 400 and 900. For these cases, the Roman numeral representations are "IV" (4), "IX" (9), "XL" (40), "XC" (90), "CD" (400) and "CM" (900). So the Roman numeral representations for 24, 39, 44, 49, and 94 are "XXIV", "XXXIX", "XLIV", "XLIX", and "XCIV", respectively. Note that at most three consecutive characters "I", "X" or "C" may appear in the numeral, and each numeral contains characters "V", "L" and "D" at most once, but arbitrarily many "M"'s may appear in it. Also, it is forbidden to use, e.g., "IC" for 99.
In middle-ages, the year a building was constructed was often indicated in an inscription: some of the characters in the inscription were emphasized, and when these characters were concatenated, they formed the number of the year in roman numerals. For example, a building with inscription "Matfyz is the best schooL In prague" was clearly founded in year "MLI", i.e., 1051. However, the inscription often gets damaged and it is no longer clear which of the letters were emphasized. The archaeologists would in that case like to know at least the latest date in that the building could be constructed, by determining the largest numeral that can be encoded in an inscription in this way. For example, if they find an inscription "matfyz is the best school in prague", they know that the building was founded at latest in year "MCLI", i.e., 1151.
The input consists of several nonempty lines l1,..., ln. Each of the lines consists of lowercase letters and spaces. The length of each line is at most 10 000 characters.
For each line li of the input, write a line consisting of a single integer to the output. This integer must be the largest roman numeral that can be encoded in the inscription given by li, or 0 if no roman numeral can be encoded in it.
matfyz is the best school in prague no year
1151 0