Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: pomedziai.in

Rezultatų failas: pomedziai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Pomedžiai

Jums duotas medis (jungus grafas be ciklų), kurį sudaro N viršūnių, o šio medžio šaknis yra r. Viršūnės u pomedžiu vadinama medžio dalis, kurią sudaro visos viršūnės v tokios, kad kelyje tarp r ir v yra viršūnė u. Paprastai tariant, viršūnės u pomedis yra visos viršūnės, esančios "po" viršūne u žiūrint iš šakninės viršūnės r.

Jūsų užduotis - kiekvienai viršūnei rasti jos pomedžio dydį.

Pradiniai duomenys

Pirmoje eilutėje įvesti du sveikieji skaičiai N ir r - viršūnių kiekis ir šaknins viršūnės numeris (1\\leqN\\leq2\\cdotp10^5,1\\leqr\\leqN).

Toliau seka N-1 eilučių. i-ojoje iš jų pateikiami du sveikieji skaičiai u ir v, kurie reiškia, kad viršūnes u ir v jungia briauna (1\\lequ,v\\leqN).

Rezultatai

Jūsų programa turi išvesti N eilučių. i-ojoje eilutėje turi būti skaičius, reiškiantis viršūnės i pomedžio dydį.

Pastaba. Atkreipkite dėmesį, kad uždavinys reikalauja daug išvesties, tad naudokite greitą išvedimo būdą.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas
8 1
1 2
1 3
1 4
2 5
2 7
5 6
4 8
8
4
1
2
2
1
1
1
Šakninė viršūnė paryškinta:
pirmas pavyzdys
5 2
1 4
1 5
1 3
3 2
3
5
4
1
1
antras pavyzdys