Cei n deţinuţi ai unei închisori, numerotaţi de la 1 la n, trebuie să sape un şanţ dispus în linie dreaptă între două puncte A şi B, situate la distanţa de 250 km unul de celălalt, pe care există 251 borne kilometrice numerotate de la 0 la 250. Fiecare deţinut are însă o pretenţie, ″e doar democraţie, nu?″: el doreşte să sape doar undeva în zona dintre borna x şi borna y. Pe lângă aceste pretenţii închisoarea se confruntă şi cu o altă problemă: nu are suficienţi paznici angajaţi.
Cerinţă
Cunoscându-se numărul n de deţinuţi şi pretenţiile lor, să se determine locul/locurile unde vor fi puşi deţinuţii să sape într-o zi de muncă, respectându-se pretenţiile lor, astfel încât numărul de paznici necesari pentru a păzi cei n deţinuţi să fie minim. Intervalul în care poate păzi un paznic nu poate conţine două sau mai multe zone disjuncte dintre cele exprimate de deţinuţi în preferinţele lor.
Date de intrare
Fişierul de intrare sant1.in are pe prima linie numărul n de deţinuţi. Pe fiecare dintre următoarele n linii există câte două numere naturale, ai bi, separate printr-un spaţiu (ai≤bi), care reprezintă pretenţia deţinutului. Mai exact pe linia i+1 (1 ≤ i ≤ n) este descrisă pretenţia deţinutului cu numărul de ordine i.
Date de ieşire
Fişierul de ieşire sant1.out va conţine pe prima linie numărul natural k reprezentând numărul minim de paznici necesari pentru paza celor n deţinuţi scoşi la lucru. Pe următoarele 2k linii vor fi descrise locurile unde vor fi puşi să sape deţinuţii, astfel: fiecare pereche de linii (2j, 2j+1) va conţine pe linia 2j trei numere naturale p xj yj, separate prin câte un spaţiu reprezentând numărul de ordine al paznicului şi bornele kilometrice xj) şi yj unde va păzi paznicul p, iar pe linia 2j+1 vor fi scrise numerele de ordine ale deţinuţilor care sapă în această zonă, separate prin câte un spaţiu, ordonate crescător.
Restricţii
1 ≤ n ≤ 10000
0 ≤ ai ≤ bi ≤ 250, pentru orice i, 1 ≤ i ≤ n
0 ≤ xj ≤ yj ≤ 250, pentru orice j, 1 ≤ j ≤ k
Un deţinut poate să sape şi într-un singur punct (″în dreptul bornei kilometrice numerotată cu x″)
În cazul în care există mai multe soluţii se va afişa una singură
Numerele de ordine ale paznicilor vor fi scrise în fişier în ordine crescătoare
Numerotarea paznicilor începe de la 1
Exemple
sant1.in
sant1.out
Explicaţii
3
0 20
8 13
30 60
2
1 8 13
1 2
2 30 60
3
sunt necesari 2 paznici: paznicul 1 va păzi între borna 8 şi borna 13, iar deţinuţii păziţi sunt 1 şi 2; paznicul 2 va păzi între borna 30 şi borna 60, iar deţinutul păzit este 3
4
10 20
2 5
30 40
5 7
3
1 10 20
1
2 5 5
2 4
3 30 40
3
sunt necesari 3 paznici: paznicul 1 va păzi între borna 10 şi borna 20, iar deţinutul păzit este 1; paznicul 2 va păzi la borna 5, iar deţinuţii păziţi sunt 2 şi 4; paznicul 3 va păzi între borna 30 şi borna 40, iar deţinutul păzit este 3
5
10 30
30 32
0 30
27 30
27 28
2
1 30 30
1 2 3 4
2 27 28
5
sunt necesari 2 paznici: paznicul 1 va păzi la borna 30, iar deţinuţii păziţi sunt 1, 2, 3 şi 4; paznicul 2 va păzi între borna 27 şi borna 28, iar deţinutul păzit este 5
!Soluţia nu este unică!