brad

Bradul de Crăciun se împodobește tradițional în Ajunul Crăciunului (24 decembrie), dar în zilele noastre multă lume îl decorează mai devreme, adesea în perioada 1-6 decembrie, pentru a se bucura de atmosfera festivă, mai ales dacă folosesc brazi artificiali, dar brazii naturali se recomandă a fi împodobiți chiar înainte de Crăciun pentru a nu se usca.

Crăciunul se apropie cu pași repezi, iar diseară plănuiești să împodobești bradul. Tu ai globuri de două culori: roșii și albastre. Pe fiecare creangă trebuie să pui fie un glob roșu, fie un glob albastru (dar nu poți să le pui pe ambele). Totuși, nu orice colorare îți place. Știi că unele crengi se ating, iar pentru a face bradul mai colorat, te-ai decis să nu pui globuri de aceeași culoare pe două crengi care se ating.

Dacă bradul poate fi decorat cu globuri astfel încât oricare două crengi care se ating să aibă globuri de culoare diferită, atunci bradul se numește decorabil.

Cerință

Se dau $C$ -- întrebarea la care vrei să răspunzi, $N$ -- numărul de crengi ale arborelui, $M$ -- numărul de perechi de crengi care se ating în arbore și $M$ perechi $(x, y)$ de crengi, reprezentând crengile care se ating.

• Dacă $C = 1$, să se afle dacă bradul este decorabil sau nu.
• Dacă $C = 2$, știi deja sigur că bradul este decorabil, dar vrei să rearanjezi puțin de tot crengile, astfel încât o nouă pereche $(x, y)$ de crengi să se atingă (înainte nu se atingeau). Să se afle în câte moduri se poate alege această nouă pereche de crengi astfel încât bradul să fie în continuare decorabil.

Nu se garantează că bradul este conectat$^1$.

Date de intrare

Pe prima linie a fișierului de intrare brad.in se află numărul $C$. Pe a doua linie a fișierului se află numerele naturale $N, M$. Pe următoarele $M$ linii se vor afla perechi de valori $x$ $y$, separate printr-un spațiu, reprezentând două crengi care se ating.

Date de ieșire

Să se afișeze în fișierul brad.out răspunsul la cerința $C$.

Restricții și precizări

• $C \in \{1, 2\}$;
• $1 \leq N, M \leq 200 \ 000$;
• Dacă se două crengi $(x, y)$ se ating, atunci nu va exista în fișier și mențiunea că $(y, x)$ se ating (e de la sine înțeles).
• O creangă nu se poate atinge de ea însăși.
• $^1$Un brad se numește conectat dacă de la orice creangă se poate ajunge la orice altă creangă printr-o serie de crengi care se ating una pe alta.

Exemplul 1

brad.in

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

brad.out

DA

Explicație

Punem globuri albastre pe ramurile cu numere impare, iar pe cele pare globuri roșii.

Exemplul 2

brad.in

1
5 4
2 5
5 1
4 2
2 1

brad.out

NU

Explicație

Oricum am încerca să aranjăm globurile, nu vom reuși să avem un brad decorabil.

Exemplul 3

brad.in

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

brad.out

1

Explicație

Pentru împodobirea de la exemplul $1$ putem rearanja crengile $(5, 4)$, iar bradul va continua să fie decorabil.