- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
خانواده قدیمی پردیس شجرهنامه طویلی داشته که سوخته است. از آنجایی که این خانواده بسیار بزرگ بوده هیچکس ارتباطات را به طور کامل به یاد ندارد.
در یک مهمانی \(n\) نفر از اعضای خانواده به منظور بازسازی شجره نامه دورهم گرد آمدهاند. هر نفر با دیدن افراد، مقداری از روابط بین افراد مهمانی در شجره را به یاد میآورد. هر گفته یکی از دو نوع زیر است
- فرد \(x\) پدر فرد \(y\) است.
- فرد \(x\) پدربزرگ فرد \(y\) است. هر دو فرد \(x\) و \(y\) در مهمانی حضور دارند.
دقت کنید ممکن است همه افراد خانواده در مهمانی حضور نداشته ولی در اطلاعات بیانشده هر دو فرد در مهمانی حضور دارند.
اطلاعات ممکن است تکراری و یا بعضاً غیر کاربردی باشند. اما همیشه درست اند. و تضمین شده که حداقل یک درختِ ریشهدار (شجرهنامه) وجود دارد که همهٔ گفتهها در آن برقرارند. همچنین دادهها بهگونهای هستند که از هر فردی در مهمانی با استفاده از ارتباطات گفتهشده میتوان به هر فرد دیگری در مهمانی رسید.
در آخر بعد از جمعآوری تمام داده ها، پیر پردیس وارد میشود. به خاطر ابهت او، هیچکسی نمیتواند قضیه سوختن شجرهنامه را لو بدهد. پیرِ پردیس چند سؤال میپرسد و اعضای پردیس باید به بهترین شکل پاسخ دهند. در هر سؤال نام دو نفر از اعضای مهمانی \(s\) و \(t\) را میدهد و میپرسد «فاصلهٔ این دو نفر در شجرهنامهٔ اصلی چقدر است؟»
از آنجا که شجرهنامهٔ اصلیِ دقیق معلوم نیست، شما باید با توجه به اطلاعات موجود، برای هر سؤال کمترین و بیشترین فاصلهای را که s و t ممکن است در بین همهٔ درختهای سازگار داشته باشند محاسبه کنید تا پردیسها از بین این دو عدد حدس درستی بزنند و به پیر پردیس بدهند.
ورودی
در سطر اول عدد صحیح \(n\) میآید که تعداد پردیسها در درخت شجرهنامه را نشان میدهد.
در سطر دوم \(n\) رشته متفاوت میآیند که نام افراد در خانواده حاضر در مهمانی را نشان میدهند. (طول هر اسم ≤ 20).
در سطر سوم عدد صحیح \(m\) میآید که تعداد دادههای موجود که اعضای خانواده به یاد میآورند را نشان میدهد.
در هر یک از \(m\) سطر بعدی، یک داده به یکی از دو صورت زیر میآید:
- \(x \text{ pedarbozorg } y\)
- \(x \text{ pedar } y\)
در سطر بعدی عدد صحیح \(q\) میآید که تعداد سوالات پیر پردیس را نشان میدهد.
در هر یک از \(q\) سطر بعدی دو رشته \(s\) و \(t\) میآید که سوالات پیر پردیس را نشان میدهند.
\[ 1 \le n, m, q \le 10^5\] \[1 \leq |s|, |t| \le 20\]
تضمین میشود که گفتههای پردیسها و نامهای افراد معتبرند و حداقل یک درخت ریشهدار وجود دارد که شرایط همه گفتهها را داشتهباشد.
خروجی
در \(q\) سطر بهترتیب برای هر سوال پیر پردیس، دو عدد چاپ کنید که اولین عدد کمترین فاصلهای که این دو نفر میتوانند در بین درختهای ممکن داشته باشند و دومین عدد بیشترین فاصلهای که میتوانند داشته باشند است.
مثالها
ورودی نمونه ۱
3
eyd norooz baastaani
2
baastaani pedarbozorg norooz
baastaani pedarbozorg eyd
1
eyd norooz
خروجی نمونه ۱
2 4
گفتهها میگویند baastaani پدر بزرگ هر دوِ khame و shir است. حال در ماکسیمم حالت پدر هیچ کدام از آنها در مهمانی حضور ندارد که با مسیر چهار در درخت خانوادگی میتوانند به هم برسد. یا با هم دیگر برادرند که در این صورت فاصله آنها دو است. در این مثال در هر صورت پدر این دو نفر نمیتواند در مهمانی حضور داشته باشد.
ورودی نمونه ۲
10
ali sabze amin sib romina seke senjed mahi samanoo abol
9
amin pedar mahi
abol pedarbozorg mahi
romina pedar samanoo
romina pedarbozorg ali
sabze pedar ali
mahi pedarbozorg sib
seke pedarbozorg samanoo
romina pedar senjed
amin pedarbozorg seke
6
romina sib
seke sabze
ali amin
amin sib
seke sib
abol ali
خروجی نمونه ۲
2 6
2 2
5 5
3 3
1 5
6 6