CSES - Ruudukko
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Annettuna on n \times n -ruudukko, jonka joissakin ruuduissa on kolikko. Voit joka siirrolla poistaa kaikki kolikot tietyltä riviltä tai sarakkeelta.

Mikä on pienin määrä siirtoja, joiden jälkeen ruudukko on tyhjä?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ruudukon koko. Ruudukon rivit ja sarakkeet on numeroitu kokonaisluvuin 1,2,\dots,n.

Tämän jälkeen syötteessä on n riviä, jotka kuvaavat ruudukon. Jokaisella rivillä on n merkkiä: . (tyhjä) tai o (kolikko).

Tuloste

Tulosta ensin kokonaisluku k: pienin siirtojen määrä. Tulosta tämän jälkeen k riviä, jotka kuvaavat siirrot.

Tulosta jokaisella rivillä ensin 1 (rivi) tai 2 (sarake) ja sitten rivin tai sarakkeen numero. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 1 \le n \le 100

Esimerkki

Syöte:

3
..o
o.o
...

Tuloste:

2
1 2
2 3