Fişierul intrare/ieşire:zapada.in, zapada.outSursăStelele Informaticii 2005, clasele 9-10
AutorAlexandru MosoiAdăugată de
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inzapada.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content