== include(page="template/taskheader" task_id="ps") ==
Poveste şi cerinţă...
Chiar inainte de sesiunea anterioara, cei $N$ studenti din grupa 236 trebuiau sa faca fata unui nou obstacol: tema la Probabilitati si Statistica. Ca orice alta tema, rezolvarea acesteia a fost amanata pana in ultima zi. Astfel, chat-ul de WhatsApp al grupei a "explodat", toti voiau sa termine tema cat mai repede si, evident, cu cat mai putin efort depus. Cumuland informatiile despre temele fiecarui student, ei au observat urmatoarele:
* Fiecarui student i-a fost data o tema "personalizata"
* Exista in total $M$ probleme distincte selectate dintr-o culegere (fara raspunsuri la final, din pacate)
* Fiecare problema din cele $M$ se afla in cel putin o tema a unui student
* Orice problema din cele $M$ se afla in cel mult doua teme
* Fiecare tema contine cel putin o problema si cel mult doua probleme
Un elev poate rezolva acum orice problema care se afla in tema lui, dupa ce o rezolva, va incarca rezolvarea in chat-ul de WhatsApp, iar orice alt student care avea acea problema in tema nu o va mai rezolva.
h2. Cerinta
Avand la dispozitie informatii despre temele tuturor studentilor, sa se determine o atribuire optima intre fiecare problema si ce student o va rezolva, astfel incat sa se minimizeze numarul maxim de probleme pe care le rezolva un student.
h2. Date de intrare
Fişierul de intrare $ps.in$ ...
Fişierul de intrare $ps.in$ contine pe prima linie trei numere intregi, $N$ (numarul de studenti), $M$ (numarul de problme), $K$.
Pe fiecare din urmatoarele $K$ linii vor gasi cate doua numere intregi, separate printr-un spatiu, $s$ si $p$, reprezentand o asociere de tipul: tema studentului cu numarul $s$ contine problema $p$.
h2. Date de ieşire
În fişierul de ieşire $ps.out$ ...
În fişierul de ieşire $ps.out$ se va afisa pe primul rand valoarea minima a numarului maxim de probleme pe care le va rezolva un student.
Pe cea de-a doua linie se vor afisa $M$ numere separate prin cate un spatiu. Al $i$-lea numar reprezinta indicele studentului care rezolva problema $i$, in cazul optim.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 100.000$
* Daca exista mai multe distributii ale problemelor, corespunzatoare solutiei optime, se poate afisa oricare dintre ele.
h2. Exemplu
