Cat and Mouse

In a house with many rooms live a cat and a mouse. The cat and the mouse each have chosen one room as their ``home". From their ``home" they regularly walk through the house. A cat can go from room A to room B if and only if there is a cat door from room A to room B. Cat doors can only be used in one direction. Similarly a mouse can go from room A to room B if and only if there is a mouse door from room A to room B . Also mouse doors can be used in only one direction. Furthermore, cat doors cannot be used by a mouse, and mouse doors cannot be used by a cat.

Given a map of the house you are asked to write a program that finds out

1. if there exist walks for the cat and mouse where they meet each other in some room, and
2. if the mouse can make a walk through at least two rooms, end in its ``home" room again, and along the way cannot ever meet the cat. (Here, the mouse may not ever meet the cat, whatever the cat does.)

For example, in the map, the cat can meet the mouse in rooms 1, 2, and 3. Also, the mouse can make a walk through two rooms without ever meeting the cat, viz., a round trip from room 5 to 4 and back.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of integers and defines the configuration of the house. The first line has three integers separated by blanks: the first integer defines the number of rooms, the second the initial room of the cat (the cat's ``home"), and the third integer defines the initial room of the mouse (the mouse's ``home"). Next there are zero or more lines, each with two positive integers separated by a blank. These lines are followed by a line with two -1's separated by a blank. The pairs of positive integers define the cat doors. The pair A B represents the presence of a cat door from room A to room B . Finally there are zero or more lines, each with two positive integers separated by a blank. These pairs of integers define the mouse doors. Here, the pair A B represents the presence of a mouse door from room A to room B .

The number of rooms is at least one and at most 100. All rooms are numbered consecutively starting at 1. You may assume that all positive integers in the input are legal room numbers.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output consists of two characters separated by a blank and ended by a new-line character. The first character is Y if there exist walks for the cat and mouse where they meet each other in some room. Otherwise, it is N. The second character is Y if the mouse can make a walk through at least two rooms, end in its ``home" room again, and along the way cannot ever meet the cat. Otherwise, it is N.

Sample Input (From example above)

1

5 3 5
1 2
2 1
3 1
4 3
5 2
-1 -1
1 3
2 5
3 4
4 1
4 2
4 5
5 4

Sample Output

Y Y

題目描述：

有一隻老鼠跟貓，貓只能走貓洞，鼠只能走鼠洞，也就是他們可能任何都會出現在他們可以在的地方。
但貓只會從 HOME 出發可以到達的地方，同理老鼠。最後有兩種詢問，貓鼠有沒有交會的可能？
以及老鼠有沒有可能走出門同時不會遇到貓可以到達的地方回到家？

題目解法：

我的解法是錯誤的，由於測試了很多種題意思，就先這樣了。

事實上做法應該是先測試貓跟鼠分別可以到達哪些地方，第一個問題則是找一個地方兩個人都可以到達的。

而第二個問題則是要找不經過貓可以到達的地方，做一次 BFS 看可不可以走回來。

//wrong solution, but accepted