3rd Balkan Olympiad in Informatics
Varna, Bulgaria, 5-11 October 1995

Day 2 - Problem 3 (Baseball League)

A connected transmission is constructed by n (n<=30) cylindrical units, labeled by 1,2,...,n in such a way that some pairs of units come to contact. If the units i and j contact and one of them is made going round in one of the two possible directions (Clockwise or Opposite), then the other begins to go round in the opposite direction. If a unit going round in one direction then the transmission blocks up.

You have to write a program which for a given transmission determines its behavior when a given unit i is made to go round in a given direction: blocks up or works normally. If the transmission works normally the program prints a list of units going round with the corresponding directions. Else the program has to determine the minimum number of units different from i to be removed from the blocked transmission so that all remaining units are going round when the unit i is made to go round.

Input: Input will be in ASCII file with the following format. The first line contains the number n of units and the number m of contacting pairs of units. Each of the next m lines contains two labels of pairs of contacting units. In the last line is given the number i of a unit and one of the characters C or O defining the direction in which that unit has to be made to go round. For the transmission of the two figures the input will be: 5 5 3 3 1 2 1 2 1 3 1 3 2 4 2 3 3 4 1 0 3 5 1 C

Output: The output will be on the standard output (screen) and consist of 3 or 4 lines. The first line describes the behavior of the system in one letter: W (for "Works") or B (for "Blocks"). If the system works then the second line is a list of units rotating Clockwise, whereas the third line is a list of units rotating Opposite direction after the removing is done and an additional line of output is a list of Removed units. For the above example the output should be: W B C 1 4 5 C 2 O 2 3 0 1 R 3