- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یکی از زندانهای شهر قلیلند، \(n\) زندانی وجود دارند که هرکدام در یک سلول انفرادی زندانی هستند.
این زندان شکلی عجیب دارد و به این صورت است که سلولهای زندان به دور یک دایره میباشند و سلولها از ۱ تا \(n\) به ترتیب شمارهگذاری شدهاند.
زندانیها برای ارتباط مخفیانه با یکدیگر، از قبل با استفاده از قاشق، زمین را حفر کردند و تونلهایی ساختند. نقشه فعلی تونلها به این شکل میباشد که شخصی که در سلول شمارهی \(i\) است، میتواند با استفاده از تونل، به سلول \(i-1\) ام و سلول \(i + 1\) ام برود (همچنین سلول شمارهی \(n\) و سلول شمارهی ۱ نیز به یکدیگر با تونل مسیر دارند).
حال زندانیها برای ارتباط بیشتر با یکدیگر و کشیدن نقشهی فرار، میخواهند تعدادی تونل دیگر را با استفاده از قاشقهایشان حفر کنند. آنها میخواهند \(m\) تونل جدید بسازند به طوری که \(i\)امین تونل از میان این \(m\) تونل، سلولهای \(u_i\) و \(v_i\) را به یکدیگر وصل کند.
برای اینکه ارتباطات مخفی زندانیها فاش نشود، آنها علاقهای ندارند که همهی افراد از وجود بعضی تونلها آگاه شوند، برای همین اگر تونلی، یک تونل دیگر را قطع کند (یعنی در جایی بجز سلولها با یکدیگر تلاقی داشته باشند) زندانیها ناراحت میشوند و آشوب به پا میکنند.
مسیر و شکل تونلها به هر صورتی میتواند باشد، یعنی ممکن است از درون دایرهای که سلولها در آن هستند تونل رد شود و یا ممکن است از خارج دایره، تونلها ساخته شوند.
زندانیها مشغول تیز کردن قاشقهای خودشان میباشند، برای همین آنها از شما کمک میخواهند تا به آنها در نحوهی ساختن تونلها کمک کنید. شما با دریافت \(m\) تونل جدیدی که قرار است رسم شود، باید بگویید که آیا میتوان تونلها را به نحوی ساخت که زندانیها ناراحت نشوند یا خیر. همچنین در صورتی که راهی برای ایجاد تونلها بدون ایجاد ناراحتی وجود دارد، باید بگویید که هرکدام از تونلها را از درون دایره رسم کنند یا بیرون دایره.
ورودی
در خط اول دو عدد \(n\) و \(m\) میآید که به ترتیب تعداد زندانیها و تونلهای جدید است.
در خط \(i\)ام از \(m\) خط بعدی، دو عدد \(u_i\) و \(v_i\) داده میشود که دو سر تونل \(i\)ام میباشد.
توجه کنید در میان تونلهای جدید ممکن است تونلی دو سلول مجاور که از ابتدا به یکدیگر تونل داشتهاند را وصل کند که در این صورت هم میتوانید آن را درون دایره بسازید و هم میتوانید بیرون دایره بسازید.
\[1 \le n,m \le 2\ 000\] \[1 \le u_i, v_i \le n\]
خروجی
در صورتی که در همهی حالات مختلف برای رسم تونلها، زندانیها ناراحت میشدند عبارت Impossible را چاپ کنید.
در غیر اینصورت یک رشته \(m\) حرفی متشکل از \(I,O\) چاپ کنید که حرف \(i\)ام آن \(I\) است اگر تونل درون دایره ساخته میشود و \(O\) است اگر بیرون دایره ساخته میشود.
در صورت وجود جوابهای مختلف یکی را میتوانید به دلخواه چاپ کنید.
مثال
ورودی نمونه
5 3
1 3
3 5
2 4
خروجی نمونه
IIO