Lo zoo JAG ospita $N$ scimmie. Le scimmie sono numerate da $1$ a $N$.

Il personale dello zoo ha studiato i rapporti tra le scimmie. Per ciascuna di $M$ coppie di scimmie, ha stabilito se le due scimmie si stanno simpatiche oppure no. Sulla base di queste informazioni, decidi di dividere le $N$ scimmie in due gabbie non vuote in modo che possano vivere il più pacificamente possibile. Per ciascuna di queste coppie devono essere soddisfatte le seguenti condizioni:

• Due scimmie che si stanno simpatiche devono essere messe nella stessa gabbia.
• Due scimmie che non si stanno simpatiche devono essere messe in gabbie diverse.

Determina se è possibile dividere le scimmie in questo modo.

Input

L'input è costituito da un singolo caso di test nel seguente formato.

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

La prima riga contiene due interi $N$ e $M$ ($2 \le N \le 10^5$, $1 \le M \le 10^5$), che rappresentano rispettivamente il numero di scimmie e il numero di coppie.

Ciascuna delle successive $M$ righe contiene due interi $a_i$ e $b_i$ ($1 \le a_i, b_i \le N$) e un carattere $c_i$, che è o oppure x. Se $c_i$ è o, le scimmie $a_i$ e $b_i$ si stanno simpatiche. Se $c_i$ è x, non si stanno simpatiche. È garantito che $a_i \ne b_i$ e che nessuna coppia di scimmie compare più di una volta.

Output

Se è possibile dividere le scimmie in due gabbie non vuote, stampa Yes; altrimenti, stampa No.

Esempi

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