Semafor

„Cum te-ai dus, așa te-ntorci!”
vechi proverb oltenesc

Zona Gorjului este formată din $N$ orașe, legate între ele prin $M$ drumuri unidirecționale. Drumurile sunt de două tipuri: $\text{\textcolor{red}{poteci}}$ (reprezentate prin $\text{\textcolor{red}{0}}$) și $\text{\textcolor{blue}{drumuri naționale}}$ (reprezentate prin $\text{\textcolor{blue}{1}}$). Nea Mărin pleacă dintr-un oraș și vrea să își alcătuiască un traseu cu următoarele proprietăți:

• Traseul începe și se termină în același oraș.
• La fiecare pas Nea Mărin se plimbă pe unul din drumurile ce au orașul actual ca sursă, respectând sensul lui de mers. Astfel el ajunge în orașul destinație al drumului, de unde procesul se reia la următorul pas.
• Pentru a nu se plictisi, peisajul trebuie să NU fie unul monoton. El consideră peisajul de pe traseu ca fiind monoton dacă traseul trece consecutiv prin două $\text{\textcolor{red}{poteci}}$ sau prin două $\text{\textcolor{blue}{drumuri naționale}}$.
• De asemenea, peisajul trebuie să fie echilibrat, în sensul că numărul total de drumuri parcurse din fiecare tip trebuie să fie egal.

Voi, programatori renumiți, sunteți acum puși în impas – va trebui să determinați din ce orașe de început poate Nea Mărin să își alcătuiască un traseu cu proprietățile descrise anterior.

Cerința

Date fiind cele $N$ orașe din Zona Gorjului, numerotate de la $1$ la $N$, și cele $M$ drumuri ce leagă orașele, fiecare fiind specificat prin cele două orașe pe care le leagă (adică sursa și destinația drumului) și prin tipul drumului, determinați din care orașe $x$ ar putea începe Nea Marin un traseu echilibrat și nemonoton, conform descrierii de mai sus.

Date de intrare

Pe prima linie se citesc de la tastatură numerele naturale $N$ și $M$, separate printr-un spațiu.

Pe următoarele $M$ linii urmează câte un triplet de numere naturale $a\ b\ c\$, cu numere separate prin spatii și cu semnificația că există un drum $a \rightarrow b$ ce leagă orașele $a$ și $b$, al cărui tip este $c$ ($\text{\textcolor{red}{0}}$ pentru poteci, $\text{\textcolor{blue}{1}}$ pentru drumuri naționale).

Date de ieșire

Pe singura linie se va afișa un șir format din $N$ cifre binare. A $i$-a cifra pentru $1 ≤ i ≤ N$ fiind $1$ dacă și numai dacă Nea Marin își poate alcătui un traseu echilibrat și nemonoton care pleacă din orașul $i$, de tipul celui descris în enunț. Altfel, cifra va fi $0$. Cifrele se vor afișa fără spații între ele!

Restricții și precizări

• $1 ≤ N ≤ 40 \ 000$
• $1 ≤ M ≤ 200 \ 000$
• Este posibil ca unele dintre cele $M$ drumuri $a \rightarrow b$ să aibă $a = b$, așa cum numai într-un sistem de drumuri oltenesc mai vezi. De asemenea, pentru unele perechi $(a, b)$ este posibil să fie mai multe drumuri $a \rightarrow b$.
• Observați că traseul lui Nea Mărin poate trece de mai multe ori prin același nod (vezi exemple).

Subtask 1 (15 puncte)

• $N ≤ 8, M ≤ 22$

Subtask 2 (17 puncte)

• $N ≤ 600, M ≤ 3 \ 000$

Subtask 3 (19 puncte)

• Se garantează că pentru oricare 51 de orașe distincte alese dintre cele N, există printre acestea două orașe a și b, cu proprietatea următoare: dacă există un traseu de la a la b (indiferent de tipul de drumuri care îl compun) atunci nu exista un traseu de la b la a.

Subtask 4 (20 puncte)

• Sunt exact $N$ drumuri naționale, acestea fiind $1 \rightarrow 2, 2 \rightarrow 3, ..., (N-1) \rightarrow N$ și $N \rightarrow 1$.

Subtask 5 (29 puncte)

• Fără restricții suplimentare.

Exemple

stdin

3 3
1 2 0
2 3 1
3 1 1

stdout

000

Explicații

Exista un singur traseu $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$. Indiferent din ce oraș ar începe Nea Marin traseul, acesta nu ar fi echilibrat, fiind format din doua drumuri naționale și o poteca.

stdin

2 3
1 2 0
2 1 1
2 2 1

stdout

11

Explicații

Nea Marin poate parcurge traseul $1 \rightarrow 2 \rightarrow 1$, care este atât echilibrat, cât și nemonoton, indiferent dacă este început din orașul $1$ sau din orașul $2$.

stdin

7 9
1 2 0
2 6 1
4 2 1
6 4 0
2 3 0
5 3 1
3 5 1
2 7 0
7 1 1

stdout

1101011 

Explicații

Nea Marin poate parcurge traseul $1\rightarrow 2\rightarrow 6\rightarrow 4\rightarrow 2\rightarrow 7\rightarrow 1$, care este atât echilibrat, cât și nemonoton. Astfel, pentru orașele $1, 2, 4, 6$ și $7$, la pozițiile corespunzătoare se va tipări valoarea $1$. Pentru orașele $3$ și $5$ se observă că răspunsul este $0$, deoarece nu exista poteci ce le au ca sursa.