2013年8月13日 星期二

274 - Cat and Mouse

房子中有一隻貓和一隻老鼠,貓和老鼠各自選一間房間為貓窩和鼠窩,牠們會從窩起身到房子的其他房間逛逛,而貓只能通過貓門到另一個房間,而這種貓門都是單向通行的,同樣地,老鼠也有鼠門,牠們只會使用自己的門,不會使用對方的門進出。


給房子地圖資訊,寫程式判斷下面 2 點資訊:
  1. 是否存在牠們會碰到面的房間。
  2. 老鼠有沒有可能從鼠窩出門(一定要出去到至少一個房間)並且回到鼠窩,途中不會有任何房間有貓的存在疑慮。
例如:從圖中可發現,貓和老鼠可能會在房間 1, 2, 3 碰面,而由於貓不可能出現在房間 4,因此老鼠可以從鼠窩到房間 4 後返回鼠窩。


Input

輸入第一行有一個整數,表示測資組數。測資組間會有一行空行。

對於每組測資第一行會有三個整數 n, cat, mouse,表示房間個數、貓窩、鼠窩編號。
接下來會有數行描述貓門的單向資訊,每行有兩個整數 A, B,表示 A 到 B 存在貓門單向通行,當 A = B = -1,則接下來換鼠門的單向資訊,同樣每行有兩個整數 A, B,表示 A 到 B 存在鼠門單向通行。
 

Ouput

對於每組測資輸出一行,判斷的 2 點資訊,以 'Y' 或 'N' 表示。

測資組間空一行。

Sample Input

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