Problem E
Harmoni og konflikt

Betragt en simpel, uvægtet, urettet graf $G$ uden sløjfer på knudemængden $\{0,\dots ,n-1\}$. Hver kant i $G$ kaldes enten konfliktkant eller harmonikant. En harmonisk tofarvning er en tildeling af hver knude til en af to farver, således at

1. endepunkterne af hver konfliktkant har forskellige farver,

2. endepunkterne af hver harmonikant har samme farve.

Din opgave er at afgøre, om $G$ kan harmonisk tofarves.

I de fire eksempelgrafer forneden, svarende til eksempelindlæsningerne, er konfliktkanterne vist som fuldt optrukne linjer og harmonikanterne som stiplede. De to første grafer kan harmonisk tofarves; eksempler på sådanne farvninger er vist. De to sidste grafer tillader ikke en harmonisk tofarvning.

     

Indlæsning

Først indlæses en linje med to heltal $n$ og $m$, som angiver antallet af knuder og kanter i grafen. Du kan antage $1\le n\le 100000$ og $0\le m\le 100000$. Hver af de følgende $m$ linjer beskriver en enkelt kant; formatet er tre heltal $uvc$ adskilte af mellemrum, med $0\le u<v<n$ og $c\in \{0,1\}$. Kantens endepunkter er $u$ og $v$; kanten er en konfliktkant hvis $c=1$, ellers er det en harmonikant.

Udskrift

»1« hvis grafen kan harmonisk tofarves, ellers »0«.

Testgrupper

Der er fire testgrupper af voksende generalitet.

13 15
0 1 1
0 2 1
0 5 1
0 6 1
1 3 1
3 5 1
4 5 1
4 6 1
6 7 1
7 8 1
8 10 1
9 10 1
10 12 1
11 12 1
9 11 1

1

13 18
0 1 1
0 2 1
0 5 1
0 6 1
1 3 1
3 5 1
4 5 1
4 6 1
6 7 1
7 8 1
8 10 1
9 10 1
10 12 1
11 12 1
9 11 1
6 9 0
8 9 0
3 4 0

1

4 5
0 1 1
1 2 1
2 3 1
0 3 0
0 2 0

0

3 3
0 1 1
1 2 1
0 2 1

0