توجد $2N$ كرة و$N+1$ علبة. لون كل كرة أحد الألوان $1,2,\ldots,N$، ويوجد بالضبط كرتان من كل لون. تستوعب كل علبة كرتين على الأكثر. في البداية، تحتوي كل علبة من $1$ إلى $N$ على كرتين، وتكون العلبة $N+1$ فارغة. في العلبة $i$، لون الكرة العلوية $A_i$ والسفلية $B_i$.

يمكن نقل كرة من علبة إلى أخرى بأخذ الكرة العلوية من علبة ووضعها في أعلى علبة أخرى.

يجب نقل الكرات بحيث تنتهي الكرتان من كل لون في العلبة نفسها. يجب أن تحقق كل نقلة أحد الشرطين التاليين.

• علبة الوجهة فارغة تمامًا.
• تحتوي علبة الوجهة على كرة واحدة بالضبط، ولونها هو لون الكرة المنقولة نفسه.

اكتب برنامجًا يجد أقل عدد من النقلات اللازمة لجمع الكرات من اللون نفسه في العلبة نفسها.

على سبيل المثال، تحقق النقلات التالية في الشكل أعلاه الهدف في 6 نقلات، ويستحيل تحقيقه بأقل من 6.

• انقل الكرة ذات اللون 3 من العلبة 4 إلى العلبة 6.
• انقل الكرة ذات اللون 2 من العلبة 3 إلى العلبة 4.
• انقل الكرة ذات اللون 4 من العلبة 1 إلى العلبة 3.
• انقل الكرة ذات اللون 3 من العلبة 2 إلى العلبة 6.
• انقل الكرة ذات اللون 5 من العلبة 5 إلى العلبة 2.
• انقل الكرة ذات اللون 1 من العلبة 5 إلى العلبة 1.

القيود

• جميع الأعداد المعطاة صحيحة.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• لكل $i$ ($1\le i\le N$)، توجد بالضبط قيمتان تساويان $i$ بين $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$.

المهام الفرعية

1. (2 نقطة) $N\le2$.
2. (23 نقطة) $N\le20$.
3. (15 نقطة) توجد طريقة لنقل الكرات بحيث تكون الكرات من اللون نفسه في العلبة نفسها.
4. (15 نقطة) $N\le2\,000$.
5. (45 نقطة) لا قيود إضافية.

الإدخال

يحتوي السطر الأول على $N$.

تعطي الأسطر الـ $N$ التالية لوني الكرتين في كل علبة. يحتوي السطر $i$ منها على $A_i$ و$B_i$ تفصل بينهما مسافة.

الإخراج

اطبع في السطر الأول أقل عدد من النقلات اللازمة لجمع الكرات من اللون نفسه في العلبة نفسها.

إذا تعذر ذلك، فاطبع $-1$.

أمثلة

الإدخال 1

5
4 1
3 5
2 4
3 2
5 1

الإخراج 1

6

الإدخال 2

2
1 1
2 2

الإخراج 2

0

الإدخال 3

4
2 1
3 1
2 4
3 4

الإخراج 3

-1