+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- صادق و ماهان که تحت تاثیر داستان گرینچ قرار گرفته اند، و با توجه به حال و هوای عید، تصمیم گرفته‌اند درخت کریسمس امیر را به سرقت ببرند. آن ها سوار بر وانت، به تهران پارس رفتند و دزدکی وارد خانه امیر شدند. اما در لحظه خروج متوجه معمایی شدند که امیر با استفاده از آن، درختش را قفل کرده بود. ماهان که المپیادی بوده است، معما را به سرعت متوجه شد و برای صادق به این شکل شرح داد. درختی $n$ راسی داریم که روی هر یال آن، یک کاراکتر کوچک انگلیسی نوشته شده است. همچنین رشته رمز $s_1 s_2 \dots s_m\,$ را در اختیار داریم. می‌خواهیم مسیری از این درخت (بدون تکرار یال‌ها) بیابیم که با پیمودن آن و به هم چسباندن یال‌های طی شده، رشته رمز را تولید کنیم. در واقع می‌خواهیم بدانیم مسیری با یال‌های $e_{i_1}, e_{i_2}, \dots, e_{i_m}\,$ بیابیم که رشته $c_{i_1}, c_{i_2}, \dots, c_{i_m}\,$ برابر با $s_1, s_2, \dots, s_m\,$ باشد. که $c_{i_j}$ کاراکتر نوشته روی یال $e_{i_j}$ است. شما باید در این مسئله، این مسیر را بیابید یا اعلام کنید هیچ مسیری با ویژگی گفته شده وجود ندارد. # ورودی در خط اول ورودی عدد $n$ که بیانگر تعداد رئوس درخت است به شما داده می‌شود. در خط $i$ام از $n-1$ خط بعدی، به ترتیب $u_i$ و $v_i$ و $c_i$ داده می‌شوند که نشان دهنده یال بین رئوس $v_i$ و $u_i$ با حرف $c_i$ هستند. تضمین می‌شود $c_i$ یک حرف کوچک انگلیسی است. همچنین تضمین می‌شود یال‌های داده شده تشکیل یک درخت می‌دهند. در خط آخر، رشته $s$ که تنها از حروف کوچک انگلیسی تشکیل شده است، به شما داده می‌شود. # خروجی در تنها خط خروجی دو عدد جدا شده توسط یک فاصله چاپ کنید که به ترتیب نشان دهنده راس شروع مسیر و راس انتهای مسیر هستند. در صورتی که چنین مسیری وجود ندارد، `-1 -1` چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 4 1 2 a 2 3 b 3 4 c bc ``` ## خروجی نمونه ۱ ``` 2 4 ``` ## ورودی نمونه ۲ ``` 4 1 2 a 2 3 b 3 4 c ac ``` ## خروجی نمونه ۲ ``` -1 -1 ```

حل سؤال در بانک سؤالات