JAG 动物园饲养着 $N$ 只猴子。这些猴子从 $1$ 到 $N$ 编号。

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

• 彼此喜欢的两只猴子必须被分在同一个笼子里。
• 彼此不喜欢的两只猴子必须被分在不同的笼子里。

请判断是否可以按这种方式将这些猴子分开。

输入格式

输入包含单个测试用例，格式如下。

$$ \begin{aligned} &N\ M \\ &a_1\ b_1\ c_1 \\ &a_2\ b_2\ c_2 \\ &\vdots \\ &a_M\ b_M\ c_M \end{aligned} $$

第一行包含两个整数 $N$ 和 $M$（$2 \le N \le 10^5$，$1 \le M \le 10^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。

样例

输入格式 1

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

输出格式 1

Yes

输入格式 2

2 1
1 2 o

输出格式 2

No