==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.
 
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
 
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
 
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
|
 
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/taskheader" task_id="zapada")==
 
==Include(page="template/raw")==
 
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.
 
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
 
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
0 < N < 100 000
0 < M < 350 000
0 < u, v <= 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)
 
 
 
Exemple
 
 
|zapada.in|zapada.out|Explicatii |
 
|5 |5 |Piticul numarul 3 va primi o ciuperca, piticul numarul 4 va primi|
| | |2 ciuperci, piticul numarul 2 va primi 3 ciuperci, piticul numarul|
|8 |3 |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|
|1 2 |1 |care sa primeasca mai putin decat el. |
| | | |
|1 4 |2 | |
| | | |
|1 3 |4 | |
| | | |
|5 2 | | |
| | | |
|2 5 | | |
| | | |
|3 5 | | |
| | | |
|4 3 | | |
| | | |
|2 3 | | |
 
 
 
==Include(page="template/taskfooter" task_id="zapada")==

708