Državno natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 3. zadatak

Promatramo tvrtku od N zaposlenika označenih brojevima od 1 do N redom po položaju, što znači da je direktor označen brojem jedan, a svaka sljedeća osoba rangirana je niže od prethodne, tj. niže od osoba s manjim rednim brojem.

Unutar tvrtke, direktorove poruke prosljeđuju se na sljedeći način.

Među zaposlenicima postoji M usmjerenih veza oblika A → B sa značenjem da osoba A može poslati poruku osobi B.

Pritom je uvijek A < B, tj. poruku šalje samo više rangirana osoba niže rangiranoj, ne i obrnuto.

Poruke se mogu prosljeđivati, npr. poruka od direktora može doći do osobe 10 na sljedeći način: 1 → 3 → 4 → 10, pod uvjetom da postoje navedene tri veze.

Veze su takve da direktor može svakom zaposleniku izravno ili neizravno poslati poruku.

Kažemo da osoba A može manipulirati osobom B ako svaka poruka od direktora (osobe 1) mora najprije doći do osobe A da bi došla do osobe B.

Drugim riječima, A manipulira B ako direktor ne može izravno ili neizravno poslati poruku osobi B a da pritom osoba A nije dio dotičnog lanca prosljeđivanja.

(Specijalno, iz ove definicije slijedi da direktor manipulira svima.)

Želimo ispitati moguće nepravilnosti u radu ove tvrtke. U tu svrhu, vaš je zadatak za svaku osobu ispisati koliko ljudi ona manipulira.

ULAZNI PODACI

U prvom su retku prirodni brojevi N (2 ≤ N ≤ 500 000) i M (2 ≤ M ≤ 1 000 000), broj zaposlenika i broj veza.

U svakom od sljedećih M redaka dva su prirodna broja A i B (1 ≤ A < B ≤ N) čije je značenje da osoba A može poslati poruku osobi B. Isti par A, B neće se navesti više puta.

IZLAZNI PODACI

Za svaku od osoba od 1 do N (redom) u zaseban redak ispišite traženi broj iz teksta zadatka.

Primjeri test podataka

Ulaz

5 6
1 2
2 3
2 4
3 4
3 5
1 5

Izlaz

4
2
0
0
0

Objašnjenje

Pojašnjenje prvog primjera: Osoba 1 (direktor) manipulira svima, dok osoba 2 manipulira osobama 3 i 4, ali ne i osobom 5 jer njoj direktor može izravno poslati poruku.

Ulaz

7 7
1 2
1 3
3 4
4 5
4 6
5 6
6 7

Izlaz

6
0
4
3
0
1
0

Objašnjenje

Pojašnjenje drugog primjera: Osoba 1 manipulira svima, osoba 3 manipulira osobama 4, 5, 6 i 7, osoba 4 manipulira osobama 5, 6 i 7, dok osoba 6 manipulira osobom 7.