У зоопарку 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