+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کشور اسپادانا از $n$ شهر تشکیل شده است که $m$ جاده بین برخی از این شهرها وجود دارد. بنابراین این کشور را می‌توانیم به گرافی $n$ راسی با $m$ یال مدل کنیم. راس‌های گراف را از $1$ تا $n$ شماره‌گذاری می‌کنیم. خشایارشاه خیلی از گراف کشور اسپادانا راضی نیست. او که در جوانی به نظریه‌گراف علاقه‌مند بوده است، درختی $n$ راسی را زیر نظر گرفته و آن درخت را **ایده‌آل** می‌نامد. خشایار شاه در مورد درخت ایده‌آل، به کیوان گفته است که قطر این درخت حداکثر $4$ است. در راستای سیاست‌های ایده‌آل‌سازی خشایار شاه، او در گام اول تصمیم گرفته است که نقشه کشورش ایده‌آل شود. بنابراین او به کیوان دستور داده است که نقشه اسپادانا را به شکل درخت ایده‌آل در بیاورد. کیوان تنها می‌تواند بعضی از جاده‌های کشور - معادل یال‌های گراف - را نابود کند. به بیان دقیق‌تر کیوان باید تعدادی از یال‌های گراف اسپادانا را حذف کند به طوری که گراف باقی مانده، درختی یک‌ریخت با درخت ایده‌آل باشد. کیوان که طبیعتا نمی‌تواند این مساله را حل کند... به همین منظور او از شما می‌خواهد که مشخص کنید آیا می‌توان گراف کشور را به درخت ایده‌آل تبدیل کردیا نه‌، سپس اگر می‌توان گراف کشور را به درخت ایده‌آل تبدیل کرد، جایگشتی در خروجی مانند $p_1, p_1, ..., p_{n}$ چاپ کنید که مشخص کند راس $i$ام در گراف اسپادانا به راس $p_i$ در درخت ایده‌آل متناظر شده است. # ورودی در خط اول ورودی دو عدد $n, m$ آمده است که $n$ تعداد شهرهای اسپادانا را معلوم می‌کند و $m$ تعداد جاده‌های میان شهرها را مشخص می‌کند. سپس $n-1$ خط دیگر می‌آید که هر خط شامل دو عدد $c_i, d_i$ است که یال‌های درخت ایده‌آل را مشخص می‌کند. سپس $m$ خط می‌آید که خط $1 \le i \le m$ شامل دو عدد $a_i, b_i$ است که یعنی جاده‌ شماره $i$، دو شهر $a_i$ و $b_i$ را به هم متصل می‌کند. $$1 \le n \le 20$$ $$0 \le m \le {n \choose 2}$$ $$1 \le a_i, b_i, c_i, d_i \le n$$ + گراف اسپادانا یال چندگانه و طوقه ندارد. + قطر درخت ایده‌آل حداکثر ۴ است. # خروجی در خروجی چنان‌چه نمی‌توان گراف اسپادانا را به درخت ایده آل تبدیل کرد فقط $-1$ چاپ کنید. در غیر این‌صورت جایگشتی به طول $n$ چاپ کنید که مشخص کند هر راس گراف کشور اسپادانا به کدام راس درخت متناظر می‌شود.‌(اگر چندین جواب وجود دارد یکی را به دلخواه چاپ کنید.) # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۰ | $n \le 10$| | ۲ | ۳۰ | $n \le 17$| | ۳ | ۵۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ``` 5 6 1 5 4 2 2 1 5 3 1 5 4 1 1 3 3 5 2 1 3 4 ``` ## خروجی نمونه ``` 2 4 5 3 1 ```

حل سؤال در بانک سؤالات