zapada

Zapada

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

==Include(page="template/taskheader" task_id="zapada")==

Poveste ...

Alba-ca-zapada trebuie sa aiba grija de cei $N$ pitici si a strans din padure $N*(N+1)/2$ ciuperci pentru masa de pranz. Ea stie ca trebuie sa dea fiecarui pitic cate un numar de ciuperci astfel incat sa nu existe doi pitici care au acelasi numar de ciuperci. In plus, unii pitici merita mai multe ciuperci decat altii pentru ca au fost mai cuminti. Ea a notat in agenda ei $M$ perechi ({$u$}, {$v$}) indicand faptul ca piticul $u$ merita mai multe ciuperci decat piticul $v$. Imediat a realizat ca ea nu poate sa tina cont de toate notitele ei asa ca va elimina niste perechi cu urmatoarea coditie: daca piticul $u$ merita mai multe ciuperci decat piticii $v{~1~}$, $v{~2~}$, ..., $v{~k~}$ atunci ea va alege o modalitate de impartire a ciupercilor astfel incat cel putin unul din piticii $v{~1~}$, $v{~2~}$, ..., $v{~k~}$ sa primeasca mai putin decat piticul $u$. Evident aceasta conditie nu poate fi satisfacuta de piticul care va primi cele mai putine ciuperci, dar Alba-ca-zapada stie ca acest lucru este inevitabil si il accepta atata timp cat pentru ceilalti pitici conditia e satisfacuta.

h2. Cerinta

...
 
h2. Restrictii
 
...

Determinati cate ciuperci va primi fiecare pitic astfel incat dorinta Albei-ca-zapada sa fie indeplinita.

h2. Date de intrare

...

In fisierul $zapada.in$ se afla pe prima linie scris numarul $N$ de pitici, iar pe cea de a doua linie numarul $M$. Pe urmatoarele $M$ linii se vor afla cate doua numere intregi $u$ si $v$ cu semnificatia ca piticul $u$ merita mai multe ciuperci decat piticul $v$.

h2. Date de iesire

...

Fisierul de iesire $zapada.out$ contine $N$ linii, linia $i$ continand un numar intreg {$X{~i~}$} reprezentand numarul de ciuperci primite de piticul numarul $i$.
 
h2. Restrictii si precizari
 
* $0 < N < 100 000$
 
* $0 < M < 350 000$
 
* $0 < u, v &le; N$
 
* Piticii sunt numerotati cu numerele de la $1$ la $N$
 
* Pe toate testele de intrare va exista solutie. Daca exista mai mute solutii se va afisa doar una (oricare dintre ele)

h2. Exemplu

| zapada.in | zapada.out |
| linia1
linia2
linia3
| linia1
linia2

table(example). |_. zapada.in |_. zapada.out |
|5
8
1 2
1 4
1 3
5 2
2 5
3 5
4 3
2 3
|5
3
1
2
4

|

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

h3. Explicatie
 
Piticul numarul 3 va primi o ciuperca, piticul numarul 4 va primi 2 ciuperci, piticul numarul 2 va primi 3 ciuperci, piticul numarul 5 va primi 4 ciuperci, piticul numarul 1 va primi 5 ciuperci. Piticul 3 a primit o ciuperca si deci nu va exista un alt pitic care sa primeasca mai putin decat el.
 
 
==Include(page="template/taskfooter" task_id="zapada")==
 
 

708