== include(page="template/taskheader" task_id="ghizi") ==
Poveste şi cerinţă...
Se caută ghizi pentru Olimpiada Naţională de Informatică. Deoarece la Olimpiadă participă $K$ echipe, trebuie ca în fiecare moment de timp din intervalul $[0, 100)$ să existe exact $K$ ghizi. Pentru posturile de ghid s-au înscris $N$ voluntari, care au fost numerotaţi distinct de la $1$ la $N$. Fiecare dintre cei $N$ voluntari a specificat un interval de timp în care poate asigura servicii de ghid. Voluntarul $i$ poate fi ghid în intervalul $[T1{~i~}, T2{~i~})$ (intervalul este închis în $T1{~i~}$ şi deschis în $T2{~i~}$).
h2. Cerinţă
Dându-se intervalele de timp asociate celor $N$ voluntari, determinaţi o variantă de angajare astfel încât în fiecare moment de timp să fie prezenţi exact $K$ ghizi. Numărul total de voluntari angajaţi este irelevant.
h2. Date de intrare
Fişierul de intrare $ghizi.in$ ...
Prima linie a fişierului de intrare $ghizi.in$ conţine două numere întregi $N$ şi $K$, separate printr-un spaţiu, cu semnificaţiile de mai sus. Voluntarii sunt numerotaţi distinct, de la $1$ la $N$. Fiecare dintre următoarele $N$ linii conţine descrierea unui voluntar; mai exact linia i+1 conţine valorile întregi $T1{~i~}$ şi $T2{~i~}$ pentru voluntarul $i$.
h2. Date de ieşire
În fişierul de ieşire $ghizi.out$ ...
În fişierul de ieşire $ghizi.out$ veţi afişa pe prima linie numărul total de ghizi angajaţi - să-l notăm cu $M$. Pe a doua linie veţi scrie $M$ numere distincte între $1$ şi $N$, ordonate crescător, reprezentând numerele de ordine ale ghizilor angajati.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 5000$
* $0 ≤ T1 < T2 ≤ 100$ pentru fiecare dintre cei $N$ voluntari
* $1 ≤ K ≤ N$
* Pot exista 2 voluntari cu acelaşi interval asociat.
* Toate testele date vor avea soluţie.
* Dacă există mai multe soluţii, afişaţi una oarecare.
* La preselecţie participă numai fete.
h2. Exemplu
table(example). |_. ghizi.in |_. ghizi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 6 2
0 100
0 15
15 99
0 10
10 20
20 100
| 4
1 4 5 6
|
== include(page="template/taskfooter" task_id="ghizi") ==
