FMI NO STRESS 13 | Chit

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

Grupul nostru, "The Cracg Mafia" este format din NN persoane foarte loiale unele celorlalte. Astfel că de fiecare dată când cineva din grup oferă un serviciu unei alte persoane, ambele persoane rețin această informație pentru ca mai târziu să se revanșeze. Cu toate astea, unii membrii nu au uneori posibilitatea de a își răscumpăra datoriile, motiv pentru care au ales să vă ceară ajutorul. Voi știți că sunt MM relații de "datorie" între două persoane. Aceste relații pot fi reduse în felul următor:

  • Dacă aa îi este dator lui bb și bb îi este dator lui aa, atunci spunem că aceștia sunt chit și ambele datorii dispar.
  • Dacă aa îi este dator lui bb și bb îi este dator lui cc (cac\ne a), atunci ambele datorii dispar și sunt înlocuite de datoria lui aa față de cc (eliminăm "middle-man"-ul).

Cerință

Mafia vrea acum să afle dacă aplicând operațiile de mai sus se poate ca în final să se ajungă la situația în care nu mai există datorii între membri. Aceasta vă cere să aflați pentru ea această informație.

Date de intrare

Pe prima linie se găsesc două numere naturale, NN și MM. Pe fiecare din următoarele MM linii se află cate două numere naturale distincte aa și bb, cu semnificația unei relații de datorie dintre aa și bb (aa îi e dator lui bb).

Date de ieșire

Dacă se poate ca în final să nu mai existe datorii afișați mesajul Chit, altfel, dacă nu se poate ajunge la o asemenea situație afișați mesajul Datorii.

Restricții și precizări

  • 3N100 0003 \le N \le 100 \ 000;
  • 2M100 0002 \le M \le 100 \ 000;
  • 1a,bN1 \leq a, b \leq N;
  • Un membru al mafiei v-a oferit o informație importantă: indiferent de ordinea reducerilor, răspunsul va fi același;
  • Este posibil ca între două persoane aa și bb să existe mai multe relații de datorie. În această situație perechea (a,b)(a, b) va apărea de mai multe ori în datele de intrare;
  • Pentru teste în valoare de 1919 puncte, N10N \le 10, M15M \le 15;
  • Pentru alte teste în valoare de 3131 de puncte, N5N \le 5;
  • Pentru alte teste în valoare de 1818 puncte, M5M \le 5;
  • Pentru alte teste în valoare de 3232 de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

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

stdout

Chit

Explicație

Avem două cicluri de datorii, între membrii 11, 22 și 33, și între membrii 44 și 55. Ambele pot fi reduse iar membrii să rămână chit.

Exemplul 2

stdin

4 3
1 2
2 3
3 4

stdout

Datorii

Explicație

Oricât am încerca, la final membrul 11 va fi dator membrului 44 deci nu vom putea scăpa de toate datoriile.

Log in or sign up to be able to send submissions!