|Online Judge||Problem Set||Authors||Online Contests||User|
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:
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
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator