题目描述

JAG 动物园饲养了 $N$ 只猴子，编号为 $1$ 到 $N$。

动物园工作人员调查了猴子之间的关系。对于 $M$ 对猴子，他们已经确定了这两只猴子是否互相喜欢。根据这些信息，你决定将这 $N$ 只猴子分配到两个非空的笼子中，使它们尽可能和平地生活。对于这些猴子对，必须满足以下条件：

• 互相喜欢的两只猴子必须放在同一个笼子里。
• 互不喜欢的两只猴子必须放在不同的笼子里。

判断能否按上述方式分配猴子。

输入格式

输入包含一组测试数据，格式如下。

N M
a_1 b_1 c_1
a_2 b_2 c_2
...
a_M b_M c_M

第一行包含两个整数 $N,M$（$2\le N\le10^5$，$1\le M\le10^5$），分别表示猴子的数量和已调查的猴子对数。

接下来 $M$ 行，每行包含两个整数 $a_i,b_i$（$1\le a_i,b_i\le N$）和一个字符 $c_i$，其中 $c_i$ 为 o 或 x。如果 $c_i$ 为 o，则猴子 $a_i$ 和 $b_i$ 互相喜欢；如果 $c_i$ 为 x，则它们互不喜欢。保证 $a_i\ne b_i$，且每对猴子最多出现一次。

输出格式

如果可以将猴子分配到两个非空笼子中并满足要求，输出 Yes；否则输出 No。

5 8
2 3 x
2 5 x
1 3 x
3 4 o
1 5 x
4 5 o
3 5 o
1 4 x

Yes

2 1
1 2 o

No