سوال ۱

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

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

• سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد شهر‌ها، و $m$، تعداد جا‌ده‌ها، است.
• سپس در هر کدام از $m$ سطر بعدی، دو عدد طبیعی $u$ و $v$ آمده است که نشان‌دهنده‌ی وجود یک جاده‌ی دوطرفه بین دو شهر $u$ و $v$ است. $n − 1$ سطر اول جاده‌هایی را نشان می‌دهند که آقای مهندس و خانم دکتر از آن‌ها عبور کرده‌اند.
• هیچ شهری به خودش جاده ندارد ولی ممکن است بین دو شهر بیش از یک جاده وجود داشته باشد.
• در سطر بعدی دنباله‌ی $  t_1, t_2, \cdots , t_{n − 1} $ آمده است که نشان‌دهنده‌ی جاده‌هایی است که در هنگام مسافرت حداقل یک‌بار طی شده‌اند.
• تضمین می‌شود که گراف یال‌هایی که آقای مهندس و خانم د‌کتر از آن‌ها عبور کرده‌‌اند ($n-1$ جاده اول)، تشکیل یک درخت می‌دهد.
• $1 \leq n \leq 2 * 10^5$
• $n − 1 \leq m \leq 2 * 10^5$
• $(u \neq v) 1 \leq u, v \leq n$

در تنها سطر خروجی شهر‌هایی را که می‌توانند به عنوان شهر شروع مسافرت آقای‌ مهندس و خانم دکتر باشند به ترتیب صعودی چاپ کنید. در صورتی که هیچ شهری وجود نداشت، عدد  $− 1$ را چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $n, m \leq 2000$
• زیرمسئله دوم (۱۵ نمره): $n − 1$ جاده اول تشکیل یک مسیر می‌دهند.
• زیرمسئله سوم (۱۵ نمره): $n = m$
• زیرمسئله چهارم (۶۰ نمره): بدون محدودیت اضافی

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

• سوال بعد