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