==Include(page="template/taskheader" task_id="zapada")==
== include(page="template/taskheader" task_id="zapada") ==
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.
Poveste ...
h2. Cerinta
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
h2. Restrictii
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$
h2. Date de intrare
* $0 < u, v ≤ N$
...
* Piticii sunt numerotati cu numerele de la $1$ la $N$
h2. Date de iesire
* Pe toate testele de intrare va exista solutie. Daca exista mai mute solutii se va afisa doar una (oricare dintre ele)
...
h2. Exemplu
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
| zapada.in | zapada.out |
| linia1
linia2
linia3
| linia1
linia2
|
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")==
== include(page="template/taskfooter" task_id="zapada") ==
