PS

ps

== include(page="template/taskheader" task_id="ps") ==

Chiar inainte de sesiunea trecuta, 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 solutia 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.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $ps.in$ contine pe prima linie trei numere intregi, $N$ (numarul de studenti), $M$ (numarul de probleme), $K$.
Pe fiecare dintre urmatoarele $K$ linii se 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$.

Fişierul de intrare $ps.in$ ...

h2. Date de ieşire

Î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.
 

În fişierul de ieşire $ps.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* Atat studentii, cat si problemele sunt indexate incepand cu 1
* Daca exista mai multe distribuiri ale problemelor, corespunzatoare solutiei optime, se poate afisa oricare dintre ele.
* Pentru teste in valoare de $30$ puncte, $1 ≤ N ≤ 2.000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. ps.in |_. ps.out |

| 5 5 8
1 1
1 2
2 1
2 3
3 2
3 3
4 5
5 4
| 1
1 3 2 5 4
|
| 5 5 6
1 1
1 2
2 3
3 3
4 5
5 4
| 2
1 1 3 5 4
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="ps") ==