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

فرض کنید $G$ یک گراف ساده $n$ راسی $m$ یالی است که راس‌های آن از $1$ تا $n$ شماره گذاری شده است.

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

یک گراف به شما داده می‌شود که همیلتونی است، از شما می‌خواهیم یکی از دورهای همیلتونی آن را پیدا کنید.

ورودی

در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف $G$ است.

$$3 \leq n \leq 100$$ $$n \leq m \leq \frac{n(n - 1)}{2}$$

در $m$ سطر بعدی دو عدد $u_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال $u_i v_i$ در گراف $G$ است.

$$1 \leq u_i \neq v_i \leq n$$

تضمین می‌شود گراف داده شده ساده است. یعنی بین هر دو راس حداکثر یک یال آمده است.

خروجی

در تنها سطر خروجی یکی از جایگشت‌های اعداد $1$ تا $n$ مثل $v_1, v_2, \dots, v_n$ را چاپ کنید به طوری که تشکیل یک دور همیلتونی بدهد؛ یعنی $v_i$ و v_{(i+1)% n} برای هر $i$ از $1$ تا $n$ به یکدیگر یال داشته‌ باشند.

مثال‌ها

ورودی نمونه ۱

5 5
1 2
4 3
4 5
5 1
3 2

خروجی نمونه ۱

3 4 5 1 2

ورودی نمونه ۲

3 3
1 2
2 3
3 1

خروجی نمونه ۲

1 2 3