Problem G
Rauður og blár Hackenbush

Sýniinntak 2

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ð rauðum og bláum leggjum er skilgreint í nokkrum skrefum. Við segjum að stakur blár leggur sé $+1$, stakur rauður leggur sé $-1$. Eins segjum við að staða þar sem sá sem leikur fyrst tapar ávallt hafi gildi $0$. Með því að bera saman stöður og fá hvenær summan er núll getum við þá fundið gildi nýrra staða. Tökum sem dæmi bláan legg fest við rauðan legg sem er fest í jörð. Ef við tökum tvö eintök af þeirri stöðu og svo einn stakann bláann legg fæst staða sem hefur gildið $0$. Þar með er gildi stöðunnar sem við erum að skoða $-1/2$.

Þú færð gefna stöðu af rauðum og bláum Hackenbush. Þetta er staða í leiknum Hackenbush þar sem allir leggir eru bláir eða rauðir.

Þú þarft að ákvarða gildi leiksins. Sýna má að þetta er ávallt heiltölubrot.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $0 \leq n, m \leq 20$. 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 \leq x, y \leq n$ með $x, y \neq 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. Á eftir tölunum tveim kemur einn bókstafur sem er ávallt R eða B, sem gefur lit leggjarins. R er rauður og B er blár.

Úttak

Ef gildi leiksins er $p/2^q$ prentið p/2q þar sem $p/2^q$ er fullstytt brot. Ef brotið er heiltala, prentið gildið án /20. Gildi leiksins er ávallt á þessu formi.

4 5
-1 1 B
-1 2 R
1 2 R
2 3 B
3 4 B

1/2^1

16 20
-1 1 B
1 3 B
1 5 B
-1 2 R
2 4 R
4 6 R
5 6 B
5 7 R
6 8 R
7 9 B
8 9 B
9 10 R
10 11 R
10 11 B
11 12 R
10 13 B
13 14 B
14 14 R
10 15 R
15 16 B

-1/2^1