Problem C
Grænn Hackenbush

Sýniinntak 1

Hackenbush er leikur með leggjum af þremur litum sem tengjast í hvorn annan eða jörð. Leggirnir eru allir rauðir, bláir eða grænir. Annar leikmaður getur hoggið rauða og græna leggi og hinn leikmaðurinn bláa og græna leggi. Þegar leikmaður heggur legg er honum eytt út. Einnig er öllum leggjum sem hafa ekki leið niður í jörð um aðra leggi eytt út.

Gildi Hackenbush leiks með einungis grænum leggjum er einfaldlega Grundy-Sprague tala þess.

Þú færð gefna stöðu af Grænum Hackenbush. Þetta er staða í leiknum Hackenbush þar sem allir leggir eru grænir (báðir leikmenn geta hoggið græna leggi).

Þú þarft að ákvarða gildi leiksins. Þar sem leikurinn er aðeins með græna leggi verður þetta ávallt heiltölunimgildi.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $0\le n,m\le {10}^5$. Hér táknar $n$ fjöldi punkta þar sem leggir mætast og $m$ fjölda leggja. Næstu $m$ línur lýsa einum legg hver fyrir sig. Hver lína inniheldur tvær heiltölur $-1\le x,y\le n$ með $x,y\ne 0$ sem táknar að leggur liggji frá punkti $x$ til punkts $y$. Ef $x=-1$ liggur leggurinn frá jörðu til $y$, og öfugt.

Úttak

Ef gildi leiksins er $\ast k$ prentið *k. Gildi leiksins er ávallt á þessu formi.

10 12
-1 1
1 2
1 3
2 4
3 4
4 5
5 6
6 7
5 8
8 9
8 9
9 10

*2

1 6
-1 -1
-1 -1
-1 1
1 1
1 1
1 1

*2