P17582 [JAG 2026 Summer Camp #3] Two Friend Groups

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.

The input consists of a single test case of the following format. ```text 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.

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