در سال‌های اخیر، بازی سوپر فوتبال طرفداران بسیاری پیدا کرده است. این بازی مانند بازی فوتبال است، با این تفاوت که هر تیم از ‎$n$‎ نفر تشکیل می‌شود. همچنین شماره پیراهن بازیکنان هر تیم اعداد ‎$1$‎ تا ‎$n$‎ است. باشگاه بارسلونا، علاوه بر در اختیار داشتن قوی‌ترین تیم فوتبال جهان، دارای قوی‌ترین تیم سوپرفوتبال جهان نیز می‌باشد. هدایت این تیم بر عهده پپ گواردیولا، سرمربی سابق تیم فوتبال بارسلونا است و مانند تیم قبلی او، این تیم نیز از روش‌های پیچیده‌ای برای بازی استفاده می‌کند.

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

بعد از آخرین بازی سوپر الکلاسیکو که با باخت سنگین رئال مادرید با نتیجه ‎$k$‎ بر هیچ به پایان رسید، ژوزه مورینیو، سرمربی این تیم، از تیم آنالیز باشگاه خواست تا به بررسی گل‌های بارسلونا بپردازند. این تیم برای هر یک از ‎$k$‎ گل بارسلونا، بازیکن‌های زیر را مشخص کرده است:

• شروع‌کننده:با شروع از این بازیکن، تعدادی پاس بین بازیکنان بارسلونا داده می‌شود تا توپ به زننده گل برسد.
• ‎گل‌زن:‎ آخرین بازیکنی که بعد از شروع حرکت توپ را دریافت کرده و گل را به ثمر رسانده است.

دقت کنید که ممکن است شروع‌کننده و زننده‌ی گل یک نفر باشند.

بعد از مشخص شدن این اطلاعات، مورینیو از تیم آنالیز خواست تا برای هر یک از بازیکنان تیم بارسلونا، تعداد ضربات به توپ (پاس یا شوت) که در به ثمر رساندن گل‌ها تاثیرگذار بوده را محاسبه کنند. تیم مذبور به اندازه‌ی کافی ضعیف هست، سعی کنید تا جای ممکن به آنها کمک کنید‎!‎

• در اولین سطر ورودی عدد ‎$n$‎ می‌آید که تعداد بازیکنان تیم بارسلونا را نشان می‌دهد داده شده است.
• در هر یک از ‎$n-1$‎ سطر بعدی، دو عدد ‎$x$‎ و ‎$y$‎ آمده است که نشان می‌دهد بازیکنان شماره ‎$x$‎ و ‎$y$‎ اجازه دادن پاس به همدیگر را دارند.‎
• در خط بعدی عدد ‎$k$‎ داده می‌شود که تعداد گل‌های بارسلونا را نشان می‌دهد و در هر یک از ‎$k$‎ سطر بعدی، دو عدد ‎$a$‎ و ‎$b$‎ داده می‌شوند که شماره بازیکنان شروع کننده و زننده گل ‎$i$‎ام بارسلونا را نشان می‌دهند.
• ‎‎ در تمام تست‌ها: ‎$1 \leq n \leq 10^6$‎ و ‎$k \leq 10 ^ 5$

در تنها سطر خروجی ‎$n$‎ عدد چاپ کنید که عدد ‎$i$ام نشان دهنده تعداد ضربات تأثیرگذار به توپ توسط بازیکن ‎$i$‎ام است.

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

• سوال قبل