- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
متاسفانه یا خوشبختانه شازززیا با موفقیت به پورتال رسیدند و به دنیای آینه‌ای وارد شدند و تصمیم گرفتند با هویت جدید غازززیا به ادامه زندگی بپردازند. آن‌ها متوجه شدند که در این دنیای جدید خیلی چیزها قرینه و پالیندروم است. بخاطر همین تصمیم گرفتند یک شهر پالیندرومی هم پیدا کنند و آن را پایتخت جدیدشان یعنی غازززلند بنامند.
به یک شهر می‌گوییم پالیندروم اگر شرایط زیر وجود داشته باشد:
- درخت ریشه‌دار $T$ وجود داشته باشد و $S$ یک کپی از $T$ باشد طوری که گراف $G$ اجتماع $T$ و $S$ باشد و برگ‌های متناظر در $S$ و $T$ ادغام(مرج) شده باشند (اما ریشه اگه برگ باشد مرج نمی‌شود). در این صورت به گراف $G$ پالیندروم می‌گوییم. حالا اگر $G$ با نقشه آن شهر متناظر باشد، به آن شهر نیز پالیندروم می‌گوییم.
از آنجایی که غازززیا با کلی شهر جدید رو به رو هستند به آن‌ها کمک کنید و برنامه‌ای بنویسید که بتوان با آن مشخص کرد که آیا یک گراف دلخواه همبند غیر جهت دار، پالیندروم هست یا نه؟
نمونه ای از یک شهر پالیندروم که مثال سوم را نشان می‌دهد.
ورودی
خط اول ورودی $n$ نشان دهنده تعداد رئوس و $m$ نشان دهنده تعداد یال‌ها است. رئوس گراف با $1$ تا $n$ شماره گذاری شده‌اند.
در $m$ خط بعدی یال‌ها آمده‌اند. در هر خط آن یک $x$ و یک $y$ آمده‌اند که به معنای وجود یال بین راس $x$ و $y$ است. ($x \neq y$ و $1 \leq x,y \leq n$) همچنین تضمین می‌شود که یال چندگانه نداریم. $$3 \le n, m \le 100000$$
خروجی
در تنها خط خروجی YES چاپ کنید اگر نقشه شهر ورودی (گراف ورودی) پالیندروم بود و در غیر آن NO چاپ کنید.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۳۰ | $$ 3 \le n,m \le 300 $$ |
| ۲ | ۳۰ | $$ 3 \le n,m \le 3500 $$ |
| ۳ | ۴۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
خروجی نمونه ۱
NO
ورودی نمونه ۲
6 6
1 2
2 3
2 4
3 5
4 5
5 6
خروجی نمونه ۲
YES
توضیح نمونه:
درخت $1$ و $2$ و $3$ و $4$ متناظر با درخت $6$ و $5$ و $4$ و $3$ است.
ورودی نمونه ۳
22 28
13 8
8 1
1 22
1 12
1 14
13 18
13 4
4 20
20 7
13 15
15 3
15 9
9 16
9 19
22 5
12 5
14 5
5 11
11 6
18 6
7 10
10 17
17 6
3 21
21 6
16 2
19 2
2 21
خروجی نمونه ۳
YES
توضیح نمونه:
گراف این مثال در صورت سوال رسم شده است.
ارسال پاسخ برای این سؤال