+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ما در دیجی‌کالا تصمیم گرفته‌ایم علائمی در نقشه اضافه کنیم تا راننده‌های تیم لجستیک از آن‌ها استفاده کنند. یک مدل ساده‌شده‌ی نقشه به شکل یک گراف تعریف می‌شود که همه‌ی یال‌ها خیابان دوطرفه و راس‌ها نشان‌دهنده‌ی موقعیت‌هایی با نام‌های یکتا هستند. به همین دلیل، حسن -که بعد از رفتن به حوزه علمیه اسمش را به صادق تغییر داده‌است- قصد دارد تابلویی به نقشه اضافه کند به اسم «دور واجب!». در نظر بگیرید خیابان $e$ موقعیت $v$ را به موقعیت $w$ وصل می‌کند. ورودی موقعیت $v$ به خیابان $e$ تابلوی «دور واجب!» نصب می‌شود اگر با ورود به خیابان $e$ از طرف $v$، برای برگشت به موقعیت $v$ راننده مجبور باشد یک دور ۱۸۰ درجه بزند. همچنین برای ساده شدن نقشه ما قصد داریم از ایجاد اضافه‌ی تابلوی «دور واجب!» پرهیز کنیم؛ این کار را با این قانون انجام می‌دهیم که اگر در ورودی موقعیت $v$ خیابان $e$ تابلوی «دور واجب!» نصب شود و در ورودی موقعیت $x$ از خیابان $f$ نیز تابلوی «دور واجب!» نصب شده‌باشد، با فرض این که بتوان از ورودی موقعیت $v$ و گذر از خیابان $e$ بدون دور زدن به موقعیت $x$ و سپس به خیابان $f$ رسید، تابلوی «دور واجب!» ورودی $x$ اضافه است. در این سوال حسن از شما می‌خواهد که به او در پیدا کردن جاهایی که باید این تابلو را نصب کنیم کمک کنید.  # ورودی در اولین خط از ورودی دو عدد $m$ و $n$ داده می‌شود که $n$ تعداد موقعیت‌ها و $m$ تعداد خیابان‌ها است. در $m$ خط بعدی دو عدد $v$ و $w$ داده می‌شود که نشان‌دهنده‌ی این است که یک خیابان دو طرفه بین دو موقعیت $v$ و $w$ است. هم‌چنین همه‌ی جفت موقعیت‌ها در ورودی یکتا هستند. $$1 \le n, m \le 5*10^5 $$ # خروجی در خط اول خروجی $k$ است که نشان‌دهنده‌ی تعداد تابلوهای مورد نیاز است. در $k$ خط بعدی در هر خط دو عدد صحیح $v$ و $w$ خروجی داده می‌شود که نشان‌دهنده‌ی این است که تابلوی «دور واجب!» باید در ورودی موقعیت $v$ به خیابان بین $v$ و $w$ نصب شود. خط‌های خروجی موقعیت تابلوها باید برحسب $v$ به شکل صعودی، و در صورت برابر بودن $v$ به صورت صعودی بر حسب $w$ چاپ شوند. # مثال ## ورودی نمونه ۱ ``` 6 5 1 2 1 3 2 3 4 5 5 6 ``` ## خروجی نمونه ۱ ``` 2 4 5 6 5 ``` ## ورودی نمونه ۲ ``` 8 8 1 2 1 3 2 3 3 4 1 5 1 6 6 7 6 8 ``` ## خروجی نمونه ۲ ``` 3 1 5 1 6 3 4 ```