Labels

یک درخت $n$ راسی به شما داده شده که هر کدام از رئوس آن یک برچسب از حروف ’a’ تا ’z’ دارد. شما باید $m$ پرسمان به صورت‌های زیر را اجرا کنید:

برچسب راس $1 \leq x \leq n$ را برابر با ’a’ $\leq y \leq$ ’z’ قرار بده. میانگین فاصله راس $x$ از رئوسی که برچسب آن‌ها ’a’ $\leq y \leq$ ’z’ است را چاپ کن.

• در سطر اول ورودی دو عدد $0 \leq m \leq 100000$ و $1 \leq n \leq 100000$ نشان‌دهنده تعداد رئوس و تعداد پرسمان‌ها آمده است.
• در $n-1$ سطر بعدی، در هر سطر دو عدد $1 \leq u_i, v_i \leq n, u_i \neq v_i$ آمده است که‌یال‌های درخت را مشخص می‌کند.
• در سطر بعدی یک رشته به طول $n$ از حروف کوچک الفبای انگلیسی آمده است که که به ترتیب برچسب روی رئوس شماره $1$ تا $n$ را مشخص می‌کند.
• در هر یک از $m$ سطر یک پرسمان به صورت زیر مطرح شده است:
  • c x y که پرسمان اول را مشخص می‌کند که x یک راس و y یک حرف کوچک الفبای انگلیسی است.
  • a x y که پرسمان دوم را مشخص می‌کند که x یک راس و y یک حرف کوچک الفبای انگلیسی است.

به ازای هر پرسمان از نوع دوم، اگر هیچ راسی با برچسب مورد نظر وجود نداشتن عدد $-1$ را در خروجی چاپ کنید. در غیر صورت پاسخ سوال را به صورت $A/B$ که $A$ و $B$ اعدادی نسبت به‌هم اول هستند چاپ کنید. پاسخ هر پرسمان را در یک سطر جداگانه چاپ نمایید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت