در پی اینکه دانش‌پژوه‌نمایی به نام ع.ط. در اقدامی به دور از ادب بدون اجازه وارد اتاق سرور شد، مسئولین تصمیم گرفتند او را به جایی دور تبعید کنند. در این جای دور تعدادی خانه وجود دارد که نقشه‌ی همسایگی آن‌ها یک درخت است. در ابتدا ما او را به خانه‌ی یک تبعید کرده‌ایم. او که تبحر خاصی در بی‌اجازه وارد خانه‌ی مردم شدن دارد می‌تواند هر ثانیه بدون اجازه به یکی از خانه‌های همسایه برود.

در هر مرحله به او می‌گوییم بی‌اجازه به سمت خانه‌ی $v$ حرکت کن هم‌چنین برای اینکه اندکی او را اذیت کنیم، همان‌طور که او در حال رفتن به سمت $v$ است (و یا به $v$ رسیده است) بعد از $t$ ثانیه می‌گوییم مقصدت را عوض کن و به سمت خانه‌ی $u$ شروع به حرکت کن. در هربار که ما دستور جدیدی به او می‌دهیم او اعلام می‌کند در چه خانه‌ای است و سپس به سمت مقصد جدید به راه می‌افتد.

• در سطر اول ورودی دو عدد $n$ و $m$ آمده‌اند.
• در هر یک از $n-1$ سطر بعد دو عدد $u$ و $v$ آمده‌است که نشان‌دهنده‌ی وجود یک راه(یال) بین خانه‌ی $u$ و خانه‌ی $v$ است.
• سپس در هر یک از $m$ سطر بعد، یک دستور به صورت $t$ $v$ ‌آمده است یعنی $t$ ثانیه بعد از دستور قبلی به او می‌گوییم جهت حرکت خود را را به سمت خانه‌ی $v$ تغییر بده.

در $m$ سطر، خانه‌ای که او در لحظه‌ی دستور فعلی در آن قرار دارد را چاپ کنید.

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

• سوال بعد
• سوال قبل