- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقای مهندس و خانم دکتر بعد از سفر به کشور مالی ادعا میکنند که از همهی شهرهای این کشور بازدید کردهاند. مالی کشوری با $n$ شهر است به طوریکه بین بعضی از شهرهای آن، جادهی دوطرفه کشیده شدهاست. همچنین میدانیم با استفاده از اینجادهها هر دو شهری از یکدیگر قابل دسترس هستند. آقای مهندس که در زمان دانشآموزی، المپیاد کامپیوتری بوده برای دیدن شهرهای مختلف کشور مالی از الگوریتم dfs
استفاده کرده است. دقت کنید خانم دکتر هم از بچههای المپیاد زیست همان سال بوده!
برنامهای بنویسید که با گرفتن تمامی جادههای کشور مالی و جادههایی که آقای مهندس و خانم دکتر دقیقن دوبار در سفرشان از آنها عبور کردهاند (یالهای درخت dfs
)، شهرهایی را که ممکن است شهر شروع مسافرت آنها باشند، پیدا کند. جادههایی که آقای مهندس و خانم دکتر از آنها عبور کردهاند با ترتیبی دلخواه در ورودی داده میشوند نه ترتیب زمانی. همچنین در dfs
، جادههای متصل به هر شهر میتوانند به هر ترتیبی دیده شوند و به ترتیبی که در ورودی میآید ربطی ندارد.
ورودی
سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد شهرها، و $m$، تعداد جادهها، است.
سپس در هر کدام از $m$ سطر بعدی، دو عدد طبیعی $u$ و $v$ آمده است که نشاندهندهی وجود یک جادهی دوطرفه بین دو شهر $u$ و $v$ است. $n-1$ سطر اول جادههایی را نشان میدهند که آقای مهندس و خانم دکتر از آنها عبور کردهاند.
هیچ شهری به خودش جاده ندارد ولی ممکن است بین دو شهر بیش از یک جاده وجود داشته باشد.
تضمین میشود که گراف یالهایی که آقای مهندس و خانم دکتر از آنها عبور کردهاند، ($n-1$ جاده اول) یک درخت است.
$$1 \leq n \le 200\ 000$$
$$n-1 \leq m \le 200\ 000$$
$$(u \ne v)$$ $$1\leq u, v \leq n$$
خروجی
در تنها سطر خروجی شهرهایی را که میتوانند به عنوان شهر شروع مسافرت آقای مهندس و خانم دکتر باشند به ترتیب صعودی چاپ کنید.
در صورتی که هیچ شهری وجود نداشت، عدد $-1$ را چاپ کنید.
زیرمسئلهها
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۰ | $ n,m \le 2\ 000 $ |
۲ | ۱۵ | $ n -1$ جاده اول تشکیل مسیر میدهند. |
۳ | ۱۵ | $ n = m $ |
۴ | ۶۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
3 3
1 2
2 3
3 1
خروجی نمونه ۱
1 3
ورودی نمونه ۲
4 4
1 2
3 1
1 4
2 3
خروجی نمونه ۲
2 3
ورودی نمونه ۳
4 6
1 2
1 3
1 4
2 3
3 4
4 2
خروجی نمونه ۳
-1
۲۴امین دوره المپیاد کامپیوتر - آزمون ششم - ۱۳۹۳/۰۶/۱۷
ارسال پاسخ برای این سؤال