• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر

---

دو آرایه به طول \(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\) عملیات استفاده شده است، درنتیجه تنها برای زیرمسئله‌ی الف صحیح است.