Fişierul intrare/ieşire:psychtraining.in, psychtraining.outSursăFMI No Stress 6
AutorMihai CalanceaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Psychtraining

Deşi naţionala de fotbal s-a calificat la Euro 2016, fanii nu sunt prea mulţumiţi de jocul echipei. Antrenorul a fost înlocuit, după o campanie intensă de scouting, cu Marius Dumitran, care va coordona echipa din Londra. Marius a realizat că mare parte din problemele naţionalei izvorăsc din psihicul jucătorilor. Astăzi Marius vrea să rezolve rivalităţile din cadrul echipei. El a numerotat jucătorii din lotul extins cu numere de la 1 la N. Şi-a notat de asemenea cele M relaţii de rivalitate din cadrul echipei. El doreşte să organizeze un număr de meciuri în cadrul sesiunii de antrenamente, astfel încât oricare 2 jucători care sunt rivali să joace la un moment dat unul împotriva altuia. La fiecare meci el va împărţi toţi jucătorii în exact 2 echipe, nu neaparat egale, una dintre ele posibil vide.

Marius n-are timp acum să organizeze meciurile, dar vă face cinste cu o anumită băutură alcoolică dacă o faceţi voi. Deoarece jucătorii s-au cam îngrăşat din cauza aceleiaşi băuturi alcoolice, nu ar trebui să dispute prea multe meciuri. Mai exact, soluţia voastră va primi punctaj pe test doar dacă numărul de meciuri este maxim 10.

Date de intrare

Fişierul de intrare psychtraining.in va conţine pe prima sa linie numerele N şi M, reprezentând numărul de jucători din lotul lărgit al României, respectiv numărul de relaţii de rivalitate dintre aceştia. Urmează M linii, fiecare conţinând o pereche de numere X Y, semnificând faptul că jucătorul cu numărul X şi jucătorul numărul Y au o rivalitate crâncenă.

Date de ieşire

Fişierul de ieşire psychtraining.out va conţine pe prima sa linie numărul MATCHES. Acesta este numărul de partide desfăşurat în soluţia voastră, iar el trebuie să fie maxim 10. Următoarele MATCHES linii vor conţine un şir de lungime N cu caractere din mulţimea {'a', 'b'}. Dacă poziţia i a şirului conţine caracterul a, atunci al i-lea jucător va fi în prima echipa, altfel va fi în a doua echipă. Ordinea echipelor este irelevantă, i.e şirurile aba şi bab sunt identice.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ N * (N - 1) / 2

Exemplu

psychtraining.inpsychtraining.out
3 2
1 2
1 3
2
aab
aba

Explicaţie

Avem rivalităţi între jucătorii 1 şi 3, respectiv între 1 şi 2. Observăm că există soluţie cu un singur meci desfăşurat, între echipele {1} şi {2, 3} (codată prin stringul "abb" sau "baa"). Însă soluţia din exemplu este de-asemenea corectă, deoarece numărul de meciuri este mai mic sau egal cu 10.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?