+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر ---------- دو آرایه به طول $2n$ داریم که هر یک از اعداد $1$ تا $n$ دقیقاً دو بار در هر آرایه ظاهر شده‌اند. می‌خواهیم آرایه‌ی اول $a_1, a_2, \ldots , a_{2n}$ را به آرایه‌ی دوم $b_1, b_2, \ldots , b_{2n}$ تبدیل کنیم. در هر مرحله می‌توانیم یک بار عملیات $CopyPaste$ را انجام بدهیم. $$CopyPaste(i, j):\ a_i\ =\ a_j$$ در این سوال شما باید دنباله‌ای از عملیات‌های $CopyPaste$ ارائه کنید که آرایه اول را به آرایه دوم تبدیل کند. نمره شما بر حسب تعداد عملیات‌هایتان مشخص می‌شود. # ورودی در خط اول عدد طبیعی $n$ آمده است. در خط دوم $2n$ عدد طبیعی‌ ‌آمده است که آرایه‌ی $a$ را نشان می‌دهد. در خط سوم $2n$ عدد طبیعی‌ ‌آمده است که آرایه‌ی $b$ را نشان می‌دهد. $$1 \le n \le 100\ 000$$ $$1 \le a_i, b_i \le n$$ # خروجی در اولین خط خروجی عدد $m$ را چاپ کنید که تعداد عملیات‌های $CopyPaste$ را نشان می‌دهد. در هر یک از $m$ خط بعدی، به ترتیب دو عدد $i$ و $j$ را چاپ کنید که نشانگر یک عملیات $CopyPaste(i, j)$ است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | شما باید همه‌ی تست‌ها را با کمتر از $4n$ عملیات حل کنید. | | ۲ | ۳۰ | شما باید همه‌ی تست‌ها را با کمتر از $3n$ عملیات حل کنید. | | ۳ | ۴۰ | شما باید همه‌ی تست‌ها را با کمتر از $2n$ عملیات حل کنید. | # مثال ## ورودی نمونه ۱ ``` 2 1 2 2 1 2 2 1 1 ``` ## خروجی نمونه ۱ ``` 2 1 2 3 4 ``` در این نمونه کمتر از $2n$ عملیات استفاده شده؛ پس این خروجی برای همه‌ی زیرمسئله‌های سوال صحیح است. ## ورودی نمونه ۲ ``` 2 1 1 2 2 2 2 1 1 ``` ## خروجی نمونه ۲ ``` 4 3 2 1 4 2 4 4 3 ``` در این نمونه از $2n$ عملیات استفاده شده؛ پس این خروجی برای همه‌ی زیرمسئله‌های سوال صحیح است. ## ورودی نمونه ۳ ``` 4 4 4 3 3 2 2 1 1 1 1 2 2 3 3 4 4 ``` ## خروجی نمونه ۳ ``` 16 5 4 3 6 4 6 6 5 7 6 5 8 6 8 8 7 7 1 1 8 2 8 8 7 5 1 1 6 2 6 6 5 ``` در این نمونه از $4n$ عملیات استفاده شده است، درنتیجه تنها برای زیرمسئله‌ی الف صحیح است.