| Fişierul intrare/ieşire: | zapada.in, zapada.out | Sursă | Stelele Informaticii 2005, clasele 9-10 |
| Autor | Alexandru Mosoi | Adăugată de | |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
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 v1, v2, ..., vk atunci ea va alege o modalitate de impartire a ciupercilor astfel incat cel putin unul din piticii v1, v2, ..., vk 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.
Cerinta
Determinati cate ciuperci va primi fiecare pitic astfel incat dorinta Albei-ca-zapada sa fie indeplinita.
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.
Date de iesire
Fisierul de iesire zapada.out contine N linii, linia i continand un numar intreg Xi reprezentand numarul de ciuperci primite de piticul numarul i.
Restrictii si precizari
- 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)
Exemplu
| 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 |
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.
