ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Clean Code

Time limit: 0.5 second
Memory limit: 64 MB
There are n computer classrooms at the Ural State University. On Saturday, October 9, it was decided to hold n programming contests in a row! Organizers have drawn a schedule—a table of size n × n of zeroes and ones. The j-th number in the i-th row is equal to one if the j-th classroom is occupied during the i-th competition, in the other case it is equal to zero.
On Friday, a cleaning lady Zina reminded organizers that she needed to tidy up the classrooms after the contests. She planned to tidy up the first computer classroom immediately after the first contest, tidy up the second classroom after the second contest, and so on. Of course, the contests can't be held in the classroom neither while they are being tided up nor after that.
Chairman of the jury agreed with Zina. At one operation he can choose a pair of distinct integers i and j (1 ≤ i, jn), swap the i-th and j-th row in the schedule, and then immediately swap the i-th and j-th column. The chairman is able to perform at most two hundred such operations until the evening. Will he be able to make the schedule acceptable to Zina?


The first line contains an integer n (2 ≤ n ≤ 100). The following n lines contain n numbers each and define the schedule of contests.


If the chairman does not have enough time to fix the schedule, output “−1”. Otherwise, output the required number of operations t in the first row, and then output t lines with two numbers in each, specifying the values of i and j which should be chosen by the chairman for the next operation. If there are many ways to fix the schedule you should output any of them.


0 0 0
1 1 0
1 1 0
1 3
1 1 1
1 1 0
1 0 0
Problem Author: Alex Samsonov
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1781. Clean Code