cutii

Pe un raft se află un șir de $N$ cutii colorate. Fiecare cutie poate fi roșie sau verde. A $i$-a cutie din șir are un volum egal cu $V_i$ litri. Două cutii pot fi interschimbate în șir dacă și numai dacă au culori diferite

Cerință

Dându-se șirul inițial de cutii, folosind cel mult $2N$ operații de interschimbare, sortați șirul de cutii crescător în funcție de volumul acestora.

Date de intrare

Prima linie conține numărul $N$, numărul de cutii.
Cea de a doua linie conține $N$ numere, separate prin câte un spațiu, corespunzând culorilor cutiilor, în ordinea în care apar în șirul inițial. Pentru culoarea roșie se va citi $1$, iar pentru culoarea verde se va citi $2$.
Cea de a treia linie conține $N$ numere naturale corespunzând volumelor cutiilor, în ordinea în care apar în șirul inițial.

Date de ieșire

Pe prima linie se va afișa $M$, numărul de operații de interschimbare pe care le-ați efectuat.
Următoarele $M$ linii conțin câte o pereche de numere separate prin spațiu ($i$ și $j$) ce descrie o operație de interschimbare (interschimbă cutia de la poziția $i$ cu cea de la poziția $j$). Operațiile se vor afișa în ordinea în care s-au efectuat.
În cazul în care nu există nicio secvență de operații valide care să sorteze șirul de cutii, se va afișa numărul $−1$ pe prima linie.

Restricții și precizări

• $3 \leq N \leq 2 \ 000$;
• pozițiile cutiilor sunt indexate incepând cu $1$
• $1 \leq V_i \leq 10^9$ pentru fiecare $i$ de la $1$ la $N$
• pentru a primi punctajul pe un teste trebuie ca:
  • în cazul în care se poate obține un șir sortat, numărul de intreschimbări efectuare, $M$, să fie $\leq 2N$ și evident, $\geq 0$, toate interschimbările să fie valide și să se poată efectua în ordinea specificată, iar în urma aplicărilor tuturor celor $M$ interschimbări șirul de cutii să fie ordonat crescător după volumele cutiilor
  • în cazul în care nu există nicio succesiune de operații în urma cărora șirul să fie sortat, afișați $-1$.

Subtask 1 (12 puncte)

• $N = 3$

Subtask 2 (49 de puncte)

• cutiile au volume distincte
• $1 \leq V_i \leq N$, pentru fiecare $i$ de la 1 la $N$

Subtaask 3 (39 de puncte)

• fără restricții suplimentare

Exemplul 1

stdin

4
1 2 1 2
4 7 5 2

stdout

2
4 1
2 4

Exemplul 2

stdin

2
2 2
4 3

stdout

-1

Explicație

Pentru primul exemplu, inițial avem: prima cutie de culoare roșie și volum 4, a doua cutie de culoare verde și volum 7, a treia cutie de culoare roșie și volum 5, a patra cutie de culoare verde și volum 2.

Vom efectua două operații ($M = 2 \leq 2N = 8$). Prima operație interschimbă cutia de la poziția 4 cu cea de la poziția 1. Obținem următorul șir: prima cutie de culoare verde și volum 2, a doua cutie de culoare verde și volum 7, a treia cutie de culoare roșie și volum 5, a patra cutie de culoare roșie și volum 4.

A doua operație interschimbă cutia de la poziția 2 cu cea de la poziția 4. Obținem următorul șir: prima cutie de culoare verde și volum 2, a doua cutie de culoare roșie și volum 4, a treia cutie de culoare roșie și volum 5, a patra cutie de culoare verde și volum 7.

Observăm că șirul final este sortat crescător după volumele cutiilor.

Pentru al doilea exemplu, pentru a avea un șir sortat trebuie să interschimbăm cele două cutii, însă este imposibil întrucât au aceeași culoare.