В зоопарке 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$, равный либо 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