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

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

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

The first line contains two integers $N$ and $M$ ($2 \le N \le 10^5$, $1 \le M \le 10^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

If it is possible to divide the monkeys into two non-empty cages, print Yes; otherwise, print No.

Examples

Input 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

Output 1

Yes

Input 2

2 1
1 2 o

Output 2

No