Labels
یک درخت n راسی به شما داده شده كه هر كدام از رئوس آن یك برچسب از حروف ’a’ تا ’z’ دارد. شما باید m پرسمان به صورتهای زیر را اجرا کنید:
برچسب راس 1≤x≤n را برابر با ’a’ ≤y≤ ’z’ قرار بده.
میانگین فاصله راس x از رئوسی که برچسب آنها ’a’ ≤y≤ ’z’ است را چاپ کن.
ورودی
در سطر اول ورودی دو عدد 0≤m≤100000 و 1≤n≤100000 نشاندهنده تعداد رئوس و تعداد پرسمانها آمده است.
در n−1 سطر بعدی، در هر سطر دو عدد 1≤ui,vi≤n,ui≠vi آمده است كه یالهای درخت را مشخص میكند.
در سطر بعدی یک رشته به طول n از حروف كوچك الفبای انگلیسی آمده است كه كه به ترتیب برچسب روی رئوس شماره 1 تا n را مشخص میکند.
در هر یک از m سطر یک پرسمان به صورت زیر مطرح شده است:
خروجی
به ازای هر پرسمان از نوع دوم، اگر هیچ راسی با برچسب مورد نظر وجود نداشتن عدد −1 را در خروجی چاپ كنید. در غیر صورت پاسخ سوال را به صورت A/B که A و B اعدادی نسبت بههم اول هستند چاپ کنید.
پاسخ هر پرسمان را در یك سطر جداگانه چاپ نمایید.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
3 7
1 2
2 3
abc
a 1 a
a 1 b
a 1 c
c 1 b
a 1 b
a 2 b
a 2 d | 0/1
1/1
2/1
1/2
1/2
-1 |