Fişierul intrare/ieşire:	ghizi.in, ghizi.out	Sursă	ONI 2003 - baraj
Autor	Mihai Stroe	Adăugată de	Silviu-Ionut Ganceanu •silviug
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ghizi

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

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.

Date de intrare

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.

Date de ieşire

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

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.

Exemplu

Cum se trimit solutii?