Fişierul intrare/ieşire:	minuni.in, minuni.out	Sursă	ONI 2010, clasele 11-12
Autor	Adrian Airinei	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Minuni

Regele Gefghev s-a gândit să viziteze o ţară în care se întâmplă multe minuni, Ţara Minunilor. Această ţară este alcătuită din N oraşe, numerotate de la 1 la N. Între oraşele i şi i+1 (1 ≤ i < N) există o stradă modernă pe care se poate circula doar de la oraşul i la oraşul i+1. Fiind un tip isteţ, Gefghev şi-a dat seama că el poate ajunge de la orice oraş i la un oraş j (j > i) mergând în total pe j-i străzi. Tronomir, angajat al direcţiei de întreţinere a drumurilor, a pus la cale un plan de construcţie a M noi străzi pentru a-i fi mai uşor lui Gefghev să călătorească. Străzile vor fi construite rând pe rând, în M zile consecutive, în ziua i fiind construită cea de-a i-a stradă. O stradă va fi construită de la oraşul a la oraşul b (1 ≤ a < b – 1 < N) şi pe această stradă se va putea circula doar de la oraşul a către oraşul b. Fiind un tip preocupat de călătorii, Gefghev se gândeşte acum să afle, după fiecare stradă construită, între care oraşe poate ajunge acum mai repede decât putea înainte de construcţia străzii. Altfel spus, el vrea să ştie câte perechi de oraşe (x, y) (1 ≤ x < y ≤ N) şi-au schimbat distanţa minimă dintre ele. Distanţa minimă dintre două oraşe x şi y este numărul minim de străzi care trebuie să fie parcurse pentru a ajunge din oraşul x în oraşul y.

Cerinţă

Scrieţi un program care determină pentru regele Gefghev, după fiecare stradă construită, numărul de perechi de oraşe (x,y) (1 ≤ x < y ≤ N) pentru care distanţa minimă de la x la y s-a modificat după construirea străzii respective.

Date de intrare

Pe prima linie a fişierului de intrare minuni.in se află două numere întregi N şi M separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se află câte două numere naturale separate de un singur spaţiu, a şi b, cu semnificaţia că s-a construit o stradă de la oraşul a la oraşul b. Străzile sunt construite în ordinea din fişierul de intrare.

Date de ieşire

În fişierul de ieşire minuni.out se vor afla M numere naturale, câte un număr pe o linie. Pe linia i se va scrie numărul de perechi de oraşe (x,y) (1 ≤ x < y ≤ N) pentru care distanţa minimă de la x la y s-a modificat, după construirea celei de a i-a străzi din fişierul de intrare.

Restricţii

• 1 ≤ N ≤ 1 000 000 000
• 1 ≤ M ≤ 100 000
• Toate oraşele între care s-au construit străzi noi sunt distincte.
• Nu există două străzi dintre cele nou construite, una (a, b) şi cealaltă (c, d) astfel încât a ≤ c ≤ b ≤ d.
• Pentru 30% din teste M ≤ 1000.

Exemplu

Explicaţie

Există 8 oraşe. Se vor construi 3 noi străzi. După construcţia străzii 2 4, se vor modifica distanţele dintre următoarele perechi de oraşe: (1 4), (1 5), (1 6), (1 7), (1 8), (2 4), (2 5), (2 6), (2 7), (2 8).

Cum se trimit solutii?