Problem E
Ríkjafræði

Mynd fengin af commons.wikimedia.org

Jörmunrekur varði páskafríinu sínu í að kynna sér stærðfræðigrein sem kallast ríkjafræði. Hún notast mikið við örvarit til að setja fram hugmyndir með myndrænum hætti. Þessar myndir tákna ríki sem samanstanda af hlutum og örvum milli hluta. Mikilvægur eiginleiki flestra slíkra örvarita er að þau séu víxlin. Það þýðir að ef lagt er af stað frá einum hlut $A$ og farið er eftir einhverri runu örva að hlut $B$ þá á útkoman úr því ávallt að vera sú sama, óháð hvaða leið er farin. Jörmunrekur er hér að skoða tiltekið örvarit og er að velta fyrir sér hvort það sé raunverulega víxlið. Í þessu örvariti er hver hlutur hið venjulega þrívíða rúm og hver ör er hliðrun rúmsins. Örvarnar eru því gefnar á forminu $(x,y,z)$ sem merkir að punktum er hliðrað um $x$ í $x$-stefnu, $y$ í $y$-stefnu og $z$ í $z$-stefnu.

Inntak

Inntak byrjar á einni línu með tveimur heiltölum $1\le n\le {10}^5$ og $1\le m\le {10}^5$ þar sem $n$ er fjöldi hluta og $m$ er fjöldi örva. Hlutirnir eru númeraðir frá $1$ og upp í $n$. Næst fylgja $m$ línur, hver með $5$ heiltölum $1\le a,b\le n$, $-{10}^9\le x,y,z\le {10}^9$. Þetta gefur að í örvaritinu sé ör frá $a$ til $b$ sem táknar hliðrunina um $(x,y,z)$. Athugið að þar sem örin er gagntæk er sjálfkrafa einnig ör frá $b$ til $a$ sem hliðrar rúminu um $(-x,-y,-z)$.

Úttak

Skrifið út Jebb ef ritið er víxlið, annars Neibb.

Stigagjöf

Útskýring á sýnidæmum

Í fyrra sýnidæminu eru tvær leiðir frá $1$ til $4$. Sama hvor leið er tekin fæst hliðrun $(1,1,1)$ svo þetta rit er víxlið.

Figure 1: Sýnidæmi 1

Í seinna sýnidæminu er búið að bæta við annarri ör. Ef við ferðumst eftir henni afturábak frá $1$ til $4$ er hliðrunin $(-1,-1,-1)$ sem er ekki það sama og hinar leiðirnar. Því er þetta rit ekki víxlið.

Figure 2: Sýnidæmi 2

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

Jebb

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

Neibb