J. Tournament Transformation
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given two tournaments $$$A$$$ and $$$B$$$ on the same set of vertices $$$1,2,\ldots,n$$$. Recall that a tournament is an orientation of the complete graph: for every pair of distinct vertices $$$i$$$ and $$$j$$$, exactly one of the edges $$$i\to j$$$ or $$$j\to i$$$ exist.

You may perform the following operation on the tournament $$$A$$$ any number of times:

  • Choose three distinct vertices $$$x$$$, $$$y$$$, and $$$z$$$ such that there exists a cycle $$$x\to y\to z\to x$$$ in the current tournament $$$A$$$;
  • Reverse all three edges among these vertices. That is, orient the edges to make the cycle $$$x\leftarrow y\leftarrow z\leftarrow x$$$

Find any sequence of operations that transforms $$$A$$$ into $$$B$$$, or determine that it is impossible.

It can be shown that whenever it is possible, there exists a valid sequence using at most $$$\frac{n(n-1)}{2}$$$ operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line contains a single integer $$$t$$$ — the number of test cases.

Each test case begins with a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of vertices.

The next $$$n$$$ lines describe tournament $$$A$$$. The $$$i$$$-th of these lines contains a binary string $$$A_i$$$ of length $$$n$$$. Here, $$$A_{ij}=1$$$ means that vertex $$$i$$$ beats vertex $$$j$$$ in tournament $$$A$$$, and $$$A_{ij}=0$$$ means otherwise.

The next $$$n$$$ lines describe tournament $$$B$$$ in the same format.

It is guaranteed that both $$$A$$$ and $$$B$$$ are valid tournaments, i.e.:

  • $$$A_{ii}=B_{ii}=0$$$ for every $$$i$$$;
  • for every $$$i \ne j$$$, exactly one of $$$A_{ij}$$$ and $$$A_{ji}$$$ equals $$$1$$$;
  • for every $$$i \ne j$$$, exactly one of $$$B_{ij}$$$ and $$$B_{ji}$$$ equals $$$1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case:

  • if it is impossible to transform $$$A$$$ into $$$B$$$, output a single line containing $$$-1$$$;
  • otherwise, output a single integer $$$k$$$ ($$$0 \le k \le \frac{n(n-1)}{2}$$$) — the number of operations. Then output $$$k$$$ lines. The $$$i$$$-th of them must contain three distinct integers $$$x$$$, $$$y$$$, and $$$z$$$ such that, immediately before this operation, the current tournament contains the directed cycle $$$x \to y \to z \to x$$$.

If there are multiple valid answers, output any of them.

Example
Input
2
3
010
001
100
001
100
010
4
0111
0011
0001
0000
0011
1011
0001
0000
Output
1
2 3 1
-1