Le zoo JAG héberge $N$ singes. Les singes sont numérotés de $1$ à $N$.

Le personnel du zoo a étudié les relations entre les singes. Pour chacune des $M$ paires de singes, il a déterminé si les deux singes s'apprécient ou non. Sur la base de ces informations, vous décidez de répartir les $N$ singes dans deux cages non vides afin qu'ils puissent vivre aussi paisiblement que possible. Pour chacune de ces paires, les conditions suivantes doivent être respectées :

• Deux singes qui s'apprécient doivent être placés dans la même cage.
• Deux singes qui ne s'apprécient pas doivent être placés dans des cages différentes.

Déterminez s'il est possible de répartir les singes de cette manière.

Entrée

L'entrée consiste en un seul cas de test au format suivant.

$$ \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} $$

La première ligne contient deux entiers $N$ et $M$ ($2 \le N \le 10^5$, $1 \le M \le 10^5$), représentant respectivement le nombre de singes et le nombre de paires.

Chacune des $M$ lignes suivantes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i, b_i \le N$) ainsi qu'un caractère $c_i$, qui vaut soit o soit x. Si $c_i$ vaut o, les singes $a_i$ et $b_i$ s'apprécient. Si $c_i$ vaut x, ils ne s'apprécient pas. Il est garanti que $a_i \ne b_i$ et qu'aucune paire de singes n'apparaît plus d'une fois.

Sortie

S'il est possible de répartir les singes dans deux cages non vides, affichez Yes ; sinon, affichez No.

Exemples

Entrée 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

Sortie 1

Yes

Entrée 2

2 1
1 2 o

Sortie 2

No