Description

人在江湖，身不由己。但倘若遵守武林盟主超人的江湖规矩，就可以混得很好。超人给出了四条规定： 朋友的朋友是朋友; 朋友的敌人是敌人; 敌人的朋友是敌人; 敌人的敌人是朋友; 现在超人想对目前统领的小江湖进行调查，看看是否有人不遵守规定。

Input

第一行为T（T<=20）表示有T组测试数据。每组测试数据由Ri+1行组成，第一行为两个整数Ni，Ri（1<=Ni<=100,000，0<=Ri<=100,000）；接下来Ri行描述了Ni个江湖人士的相互关系，以“A B relation”的格式给出。如果Relation=’F’，那么表示A和B是朋友，如果Relation为’E’，那么说明A和B是敌人，而其中(A!=B,且1<=A,B<=N)。*注意，如果

Output

一共T行，如果该组数据中有至少有一个江湖人士违背了规矩，那么输出“N”；如果没有出现不遵守规矩的人那么输出“Y”。

Sample

Input

3
3 3
1 2 F
1 3 F
2 3 E
3 1
1 2 E
3 3
1 2 E
1 3 E
2 3 F

Output

N
Y
Y

Source: 超人