시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB76266.667%

문제

Juku ei ole lauamängude mängimises kuigi hea. Seega otsustas ta enne järgmist mänguõhtut oma oskusi parandada, harjutades üksi mängu "Tsirkus" mängimist.

Mäng "Tsirkus" on lihtne lauamäng: mängulaual on $N$ ruutu, nummerdatud $1$ kuni $N$. Kõigi mängijate nupud alustavad ruudult $1$. Oma käigul veeretab mängija kuuetahulist täringut ning liigutab oma nuppu edasi nii mitu ruutu, kui näitab täring silmi ($1$ kuni $6$). Mõnel ruudul aga algab kas madu või redel. Maod viivad nuppe mängulaual tagasi, redelid aga edasi. Kui mängija nupp jääb seisma ruudul, millel algab madu, peab ta liigutama oma nupu mao teise otsa. Sarnaselt, kui nupp jääb seisma ruudul, millel algab redel, peab ta liigutama oma nupu redeli teise otsa. Mängija on võitnud, kui tema nupp jõuab ruudule $N$ või ületaks seda.

Selleks, et teada, palju arenemisruumi tal veel on, soovib Juku teada, mis on vähim arv täringuviskeid, mida ta peab sooritama, et mängu võita.

입력

Sisendi esimesel real on mängulaua ruutude arv $N$ ning madude ja redelite koguarv $M$ ($2 \le N \le 10^5$, $0 \le M$). Järgmisel $M$ real on igaühel kas mao või redeli kirjeldus: täisarvud $A$ ja $L$ ($1 < A < N$, $1 \le L \le N$, $A \neq L$):

  • Kui $A < L$, siis kirjeldab rida redelit, mis algab ruudul $A$ ning viib ruudule $L$.
  • Kui $A > L$, siis kirjeldab rida madu, mis algab ruudul $A$ ning viib ruudule $L$.

On garanteeritud, et $A$ väärtused on üle kõigi ridade paarikaupa erinevad ning et ükski $L$ väärtus ei kattu ühegi $A$ väärtusega.

출력

Väljundi esimesele reale väljastada vähim vajalik täringuvisete arv mängu võitmiseks ning teisele reale tühikutega eraldatult vastav täringuvisete jada. Kui sobivaid täringuvisete jadasid on mitu, väljastada neist suvaline. Kui mängu pole võimalik võita, siis väljastada väljundi ainsale reale \verb'EI SAA'.

예제 입력 1

30 0

예제 출력 1

5
5 6 6 6 6

예제 입력 2

7 1
2 7

예제 출력 2

1
1

Selles näites on mängulaual üks redel ruudult $2$ ruudule $7$. Seega on võimalik lõppu jõuda ühe täringuviskega kas veeretades $1$, mispuhul redel viib nupu lõppu, või veeretades $6$, mispuhul nupp jõuab samuti lõppu.

예제 입력 3

31 6
5 2
6 2
7 2
8 2
9 2
10 2

예제 출력 3

EI SAA

Selles näites algavad maod ruutudel $5$ kuni $10$. Saab näidata, et sellisel juhul pole ühegi täringuvisete jadaga võimalik nupul lõppu jõuda.