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:
- vaihda keskenään kaksi riviä
- 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ä)
Osatehtävä 2 (55 pistettä)
Osatehtävä 3 (33 pistettä)
