startrek

*„Spaţiul: ultima frontieră. Acestea sunt călătoriile navei stelare Enterprise. Misiunea ei neîncetată: să exploreze lumi noi şi stranii, să caute noi forme de viaţă şi noi civilizaţii, să meargă acolo unde nimeni nu a mai fost vreodată.”

Jean-Luc Picard – căpitanul navei Enterprise stabilește noua destinație: Imperiul Stelar Romulan. Gaura de vierme nou descoperită de echipaj asigură calea de acces spre Quadrantul Beta – aria galactică unde se află Imperiul Stelar Romulan.*

Figura 1 din enunțul original al problemei startrek.Mărește schema ↗

Ipotetic, putem privi gaura de vierme ca un segment de dreaptă partiționat în N sectoare de lungimi egale numerotate de la 1 la N pe care nava le va parcurge exact în această ordine. În funcție de distorsiunile spațiutimp întâlnite, nava poate parcurge într-un an sideral (UTC – timpul universal coordonat) cel puțin p sectoare și cel mult q sectoare. Pentru fiecare sector căpitanul Picard trebuie să informeze Federația despre anul în care a fost parcurs. Datorită interferențelor transmisia datelor este deficitară. Astfel, Federația nu primește informații din toate cele N sectoare.

Cerinţă

Cunoscând descrierea a M transmisii primite de Federație de forma: s t, unde s reprezintă indicele unui sector, iar t reprezintă anul în care este parcurs acesta, să se determine numărul maxim de ani în care este străbătută gaura de vierme formată din N sectoare numerotate de la 1 la N.

Date de intrare

Fişierul de intrare startrek.in conţine pe prima linie patru numere naturale N, p, q și M, separate prin câte un spațiu, cu semnificația din enunț. Pe următoarele M linii se află descrierea celor M transmisii primite de Federație, în ordinea crescătoare a anilor și a sectoarelor.

Date de ieşire

Fişierul de ieşire startrek.out va conține două linii. Pe prima linie se va afla un număr natural nenul A ce reprezintă numărul maxim de ani siderali necesar parcurgerii celor N sectoare. Pe cea de a doua linie se vor găsi N valori despărțite prin câte un spațiu ce reprezintă descrierea temporală minimal lexicografică a sectoarelor parcurse, pentru fiecare sector fiind specificat anul.

Restricții și precizări

• 2 ≤ N ≤ 100 000
• 2 ≤ p < q ≤ N
• 1 ≤ M ≤ N
• fiecare sector trebuie parcurs în totalitate în cadrul aceluiași an sideral;
• întreaga călătorie trebuie parcursă într-un număr întreg de ani siderali (cu alte cuvinte: parcurgerea a cel puțin p sectoare și cel mult q sectoare este valabilă și pentru primul și ultimul an);
• pentru datele de intrare există întotdeauna soluție;
• pentru 30 de puncte 2 ≤ N ≤ 100, 2 ≤ p < q ≤ 50
• pentru 70 de puncte 2 ≤ N ≤ 30 000, 2 ≤ p < q ≤ 300
• pentru 100 de puncte 2 ≤ N ≤ 100 000, 2 ≤ p < q ≤ N

Exemple

startrek.in

5 2 3 1
2 1

startrek.out

2
1 1 1 2 2

Explicaţii

Știm că al doilea sector este parcurs în primul an. 1 1 2 2 3 nu poate fi soluție deoarece în anul 3 nu sunt parcurse minim 2 sectoare.
Sunt necesari 2 ani pentru parcurgerea celor 5 sectoare. Primele 3 sectoare vor fi parcurse în primul an, următoarele 2 sectoare în cel de-al doilea an.

startrek.in

7 2 5 2
2 1
6 3

startrek.out

3
1 1 1 2 2 3 3

Explicaţii

Sunt necesari 3 ani pentru parcurgerea celor 7 sectoare.
Primele 3 sectoare vor fi parcurse în primul an, următoarele 2 sectoare în cel de-al doilea an, iar ultimele 2 sectoare în cel de-al treilea an.

startrek.in

16 3 4 2
5 2
15 5

startrek.out

5
1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5

Explicaţii

Sunt necesari 5 ani pentru parcurgerea celor 16 sectoare.