Vaihdot

• Time limit: 1.00 s
• Memory limit: 512 MB

Annettuna on kaksi $n \times n$ -ruudukkoa, joista molemmat sisältävät kokonaisluvut $1,2,\ldots,n^2$ jossain järjestyksessä. Ruudukon rivit ja sarakkeet on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Käytössäsi on seuraavat operaatiot:

1. vaihda keskenään kaksi riviä
   
2. vaihda keskenään kaksi saraketta
   

Tehtäväsi on muuttaa ensimmäinen ruudukko toiseksi operaatioiden avulla niin, että operaatioiden määrä on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: ruudukoiden koko.

Sitten syötteessä on $n$ riviä, jotka kuvaavat ensimmäisen ruudukon, ja lopuksi $n$ riviä, jotka kuvaavat toisen ruudukon.

Tuloste

Tulosta ensin kokonaisluku $k$: pienin operaatioiden määrä. Tulosta sitten $k$ riviä, jotka sisältävät operaatiot järjestyksessä.

Jokaisen operaation tulee olla muotoa "$1$ $a$ $b$" (vaihda rivit $a$ ja $b$) tai "$2$ $a$ $b$" (vaihda sarakkeet $a$ ja $b$).

Jos mitään ratkaisua ei ole olemassa, tulosta vain luku $-1$.

Esimerkki 1

Syöte:
3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6

Tuloste:
2
2 1 2
1 2 3

Esimerkki 2

Syöte:
3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6

Tuloste:
-1

Osatehtävä 1 (12 pistettä)

• $1 \le n \le 3$
  

Osatehtävä 2 (55 pistettä)

• $1 \le n \le 50$
  

Osatehtävä 3 (33 pistettä)

• $1 \le n \le 500$