minuni

Minuni

== include(page="template/taskheader" task_id="minuni") ==

Poveste şi cerinţă...

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 &le; 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 &le; 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 &le; x < y &le; 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$.
 
h2. Cerinţă
 
Scrieţi un program care determină pentru regele Gefghev, după fiecare stradă construită, numărul de perechi de oraşe $(x,y)$ $(1 &le; x < y &le; N)$ pentru care distanţa minimă de la $x$ la $y$ s-a modificat după construirea străzii respective.

h2. Date de intrare

Fişierul de intrare $minuni.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $minuni.out$ ...

Î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 &le; x < y &le; 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.

h2. 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$.

h2. Exemplu
table(example). |_. minuni.in |_. minuni.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 8 3
2 4
1 5
6 8
| 10
4
6

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

== include(page="template/taskfooter" task_id="minuni") ==

4778