Problem Description

JAG Zoo keeps $N$ monkeys. The monkeys are numbered from $1$ to $N$.

The zoo staff have investigated the relationships among the monkeys. For each of $M$ pairs of monkeys, they have determined whether the two monkeys like each other or not. Based on this information, you decide to divide the $N$ monkeys into two non-empty cages so that they can live as peacefully as possible. For each of these pairs, the following conditions must be satisfied:

• Two monkeys that like each other must be placed in the same cage.
• Two monkeys that do not like each other must be placed in different cages.

Determine whether it is possible to divide the monkeys in this way.

Input Format

The input consists of a single test case of the following format.

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

The first line contains two integers $N$ and $M$ ($2\le N\le10^5$, $1\le M\le10^5$), representing the number of monkeys and the number of pairs, respectively.

Each of the following $M$ lines contains two integers $a_i$ and $b_i$ ($1\le a_i,b_i\le N$) and a character $c_i$, which is either o or x. If $c_i$ is o, monkeys $a_i$ and $b_i$ like each other. If $c_i$ is x, they do not like each other. It is guaranteed that $a_i\ne b_i$ and that no pair of monkeys appears more than once.

Output Format

If it is possible to divide the monkeys into two non-empty cages, print Yes; otherwise, print 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