Play with Sequence

Problem Description
ivankevin loves sequences.
A sequence of n elements is called a SWITCH SEQUENCE iff:
Each element is a 2-switch, where a 2-switch is the replacement of a pair of edges xy & zw in a simple graph by the edges yz and wx, given that yz and wx did not appear in the graph originally.
Now give two simple graphs G and H with same vertex set V, ivankevin wants to know whether there is a switch sequence transforms G into H.

Input
There are multiple test cases.
Each case contains 1 + 2n lines. The positive integer n(0<n<101) is given in the first line. The next 2n lines are the matrix which describe the two graphs G and H. The j elements in the i rows is either 0 or 1. If the node i and the node j has a edge in the graph. The elements will be 1. Otherwise is 0. It’s guaranteed that the matrix is symmetry and the i elements in the i row is always 0. See sample input for more details.

Output
For each case, first output an integer L in a line, which should represent the length of the switch sequence you found.
If no switch sequence can transform G into H, then you should print L as -1 and no more lines. Otherwise output L lines follow. Each of the L lines should contains four distinct integers x, y, z and w, indicating a 2-switch on G, as described.
For some reason, if L is equal to or larger than 1000000, ivankevin would think the switch sequence you found is so ugly that it is ungelieveble and unacceptable. Otherwise, if L < 1000000 and the sequence finally transform G into H, he will accept your answer.

Sample Input
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0

Sample Output
1
0 1 3 2
-1

1个回答