齿轮系统

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个齿轮系统由n(n<=30)个齿轮组成,这些齿轮编号为1,2,...,n。我们知道,当一个齿轮转动(顺时针或逆时针)时,同时与之相邻的所有齿轮也会发生相反方向的转动(如果能转动的话):例如齿轮1与齿轮2是相邻的,那么当齿轮1顺时针转动时,相应的齿轮2应逆时针转动。如果我们转动其中的一个齿轮,在这样的规则下,不是所有的齿轮都能成功的转动起来,我们就称这个系统式阻塞的。

如图1所示,3个齿轮中的任一个都与其他2个相邻,当齿轮1顺时针转动时,齿轮2、齿轮3应逆时针转动,同理,当齿轮2逆时针转动时,齿轮3要顺时针转动,与前面矛盾,故这个系统是阻塞的。 



现请你编写一个程序,对于任意一个给出的齿轮系统,当指定齿轮i转动(顺时针或逆时针)时,判断整个系统能否正常地工作,我们认为系统正常工作的条件是所有的齿轮都能成功的转动起来。如果系统能够正常地工作,给出每一个齿轮相应的转动方向;如果系统是阻塞的,你的程序要决定在去掉最少的齿轮的情况下,使得剩下的齿轮构成的齿轮系统能够正常地工作。

Input

输入数据的第一行包括两个数字n、m,表示有n个齿轮、m对相邻关系。接下来的m行即为相邻关系,每行包括两个数字i、j,表示齿轮i、j相邻。最后一行包括一个数字i和一个字母(C或O),表示顺时针或逆时针转动第i个齿轮(称之为主动轮),C(Clockwise)表示顺时针转动、O(Opposite)表示逆时针转动。

Output

输出数据应包括3或4行。

第一行用一个字母表示给出的齿轮系统能否正常地工作,能正常地工作显示W(Works的第一个字母),不能正常地工作即阻塞显示B(Blocks的第一个字母)。如果系统能够正常地工作,第二行显示所有顺时针转动的齿轮,以C打头后面依次按顺时针转动的齿轮的编号,字母C与编号之间,编号与编号之间请用一个空格隔开;第三行显示所有逆时针转动的齿轮,以O打头后边依次按逆时针转动的齿轮的编号,空格的使用同上。如果系统阻塞,则在第四行以R(Remove的第一个字母)打头依次显示所有去掉的齿轮的编号,空格的使用仍然同上;第二第三行与系统能够正常工作时相同。对于系统阻塞的情况,可能会出现多种去掉齿轮的方案,我们只要求给出任意一种即可,当然你的程序不应该把主动齿去掉。注意:输出时若有C、O和R,各行末尾留有一个空格。

Sample Input

5 5
1 2
2 3
3 4
4 5
5 1
1 C

Sample Output

B
C 1 4 
O 3 5 
R 2

Hint

Source