Diferente pentru problema/afterparty intre reviziile #6 si #23

Nu exista diferente intre titluri.

Diferente intre continut:

Eşti la after-party-ul organizat după concurs. Stai la bar şi conversezi cu prietenul tău, Eudoxiu, zis Doxuţă. Eşti uşor frustrat fiindcă echipa lui Doxuţă te-a făcut astăzi, deşi tu ştii că a avut noroc, că testele au fost slabe şi că până la urmă o victorie la penalizare nu e victorie adevărată, nu-i aşa?.
Discuţia merge înspre a observa persoanele din club şi relaţiile dintre ele. Până acum aţi observat că sunt $N$ persoane şi $M$ relaţii de curtoazie între ele, relaţii care sunt bidirecţionale (aici am părăsit realitatea). Observaţi şi că persoanele pot fi împărţite în două mulţimi $A$ şi $B$, astfel încât persoanele din $A$ curtează/sunt curtate doar de persoane din mulţimea $B$. Doxuţă nu scapă ocazia şi se laudă că el poate determina dacă există cuplaj perfect între cele $N$ persoane. Mai mult, "te ia la caterincă" - un termen suburban de care abuzează des - şi zice că tu probabil nu ştii să găseşti un cuplaj perfect. Pe deplin revoltat de această ipoteză, îi dai mândru replica: "Boss, eu pot să determin TOATE cuplajele perfecte". Te calmezi un pic şi realizezi că de fapt nu ştii să faci asta, ba nu ştii nici să numeri câte cuplaje perfecte sunt.
Discuţia merge înspre a observa persoanele din club şi relaţiile dintre ele. Până acum aţi observat că sunt $N$ persoane şi $M$ relaţii de curtoazie între ele, relaţii care sunt bidirecţionale (aici am părăsit realitatea). Observaţi şi că persoanele pot fi împărţite în două mulţimi $A$ şi $B$, astfel încât persoanele din $A$ curtează/sunt curtate doar de persoane din mulţimea $B$. Doxuţă nu scapă ocazia şi se laudă că el poate determina dacă există cuplaj perfect între cele $N$ persoane. Mai mult, "te ia la caterincă" - un termen suburban de care abuzează des - şi zice că tu probabil nu ştii să găseşti un cuplaj perfect. Pe deplin revoltat de această ipoteză, îi dai mândru replica: "Boss, eu pot să determin TOATE cuplajele perfecte". Te calmezi un pic şi realizezi că de fapt nu ştii să faci asta, ba chiar nu ştii nici să numeri câte cuplaje perfecte sunt.
Totuşi, dacă te gândeşti un pic, parcă poţi să-i spui paritatea numărului de cuplaje perfecte.
Totuşi, dacă te străduieşti, crezi că poţi să-i spui paritatea numărului de cuplaje perfecte.
h2. Date de intrare
Fişierul de intrare $afterparty.in$ va conţine pe prima sa linie numărul de teste $T$. Urmează $T$ teste, fiecare respectând următoarea structură: pe prima linie se află numerele $N$ şi $M$, semnificând numărul de persoane şi numărul de relaţii de curtoazie. Urmează $M$ linii fiecare conţinând o pereche de nume $X Y$, semnificând faptul că $X$ şi $Y$ se curtează reciproc. $X$ şi $Y$ vor fi formate din litere mici şi mari ale alfabetului englez şi vor avea o lungime maximă de $20$ de caractere.
 
 
h2. Date de ieşire
În fişierul de ieşire $afterparty.out$ va conţine $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător: mesajul "Par", dacă numărul de cuplaje perfecte este par, respectiv "Impar" altfel.
Fişierul de ieşire $afterparty.out$ va conţine $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător: mesajul "Par", dacă numărul de cuplaje perfecte este par, respectiv "Impar" altfel.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 100$
* $0 ≤ M ≤ N * (N - 1) / 2$
* Se numeşte cuplaj perfect într-un graf bipratit o mulţime de muchii ale grafului cu proprietatea că fiecare nod este capătul *exact* unei singure muchii.
h2. Exemplu
table(example). |_. afterparty.in |_. afterparty.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
| 2
6 4
Tu CubaLibre
Mihai Restanta
CubaLibre Doxuta
Doxuta Comisia
4 3
Doxuta Comisia
Doxuta Mafia
Doxuta PorCostel
| Impar
Par
|
h3. Explicaţie
...
În primul exemplu există un unic cuplaj perfect.
În al doilea exemplu, deşi Doxuta este foarte bine conectat cu toate celebrităţile concursului, nu se poate forma niciun cuplaj perfect.
== include(page="template/taskfooter" task_id="afterparty") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.