E. Бяцхан заан ба мод

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан заан модонд үнэхээр их дуртай, ялангуяа тэрээр үндэстэй модонд дуртай юм.

Түүнд $n$ зангилааны цэгээс тогтох мод байх ба (зангилааны цэгүүд нь 1-ээс $n$ хүртэл дугаарлагдсан), уг модны үндэс нь 1 дугаартай зангилааны цэг дээр байв. Модны зангилааны цэг бүр анхандаа хоосон байх тоонуудын бүртгэлийг агуулна.

Бяцхан заан $m$ ширхэг үйлдэл хийхийг хүсжээ. $i$-дахь үйлдэл дээрээ $(1 ≤ i ≤ m)$ тэрээр $a_{i}$ дугаартай зангилааны цэг дээр үндэстэй дэд модны бүх зангилааны цэг дээрх бүртгэл дээр $i$ тоог нэмнэ, дараа нь тэрээр $b_{i}$ дугаартай зангилааны цэг дээр үндэстэй дэд модны бүх зангилааны цэг дээрх бүртгэл дээр $i$ тоог нэмнэ.

Бүх үйлдлийг хийсний дараа бяцхан заан зангилааны цэг $i$ бүрийн хувьд $c_{i}$ тоог тоолохыг хүсжээ -- энэ нь $i$-дахь болон $j$-дэх зангилааны цэгүүдийн бүртгэл нь дор хаяж нэг ижил тоо агуулсан байх бүхэл тоо $j$ $(1 ≤ j ≤ n; j ≠ i)$-ын тоог илэрхийлнэ.

Бяцхан заанд туслан, $c_{i}$ тоонуудыг түүнд тоолж өгнө үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ $(1 ≤ n, m ≤ 10^{5})$ өгөгдөнө -- эдгээр нь модны зангилааны цэг болон үйлдлийн тоог илэрхийлнэ.

Дараагийн $n - 1$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо, $u_{i}$ болон $v_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i})$ өгөгдөнө, эдгээр нь $u_{i}$ болон $v_{i}$ дугаартай зангилааны цэгүүдийн хооронд ирмэг байгааг илэрхийлнэ.

Дараагийн $m$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо, $a_{i}$ болон $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i})$ өгөгдөнө, эдгээр нь $i$-дахь үйлдлийн зангилааны цэгүүдийн индексүүдийг илэрхийлнэ.

Өгөгдсөн граф нь чиглэлгүй мод байна.

Гаралт

Ганц мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоог хэвлэнэ -- $c_{1}, c_{2}, ..., c_{n}$.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5 1
1 2
1 3
3 5
3 4
2 3
Гаралт
0 3 3 3 3 
Оролт
11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
Гаралт
0 6 7 6 0 2 0 5 4 5 5 
Сэтгэгдлүүдийг ачааллаж байна...