適切な距離感が重要だと思っているharurun君は、そのようなグラフを構築することにしました。
正整数 $N$ と、 $N$ 個の文字列 $S_1,S_2,\ldots,S_N$ が与えられます。
$S_i$ は 0と1 からなる長さ $N$ の文字列です。
以下の条件を満たす、頂点に $1$ から $N$ までの番号が付けられた、頂点数 $N$ の単純無向グラフが存在するかどうかを判定し、存在するならば $1$ つ構築してください。
1 であるならば 頂点 $i$ と 頂点 $j$ の距離は $2$ である。ここで、頂点 $u$ と頂点 $v$ の距離とは、 $u$ から $v$ への最短経路上の辺の数を指します。 ただし、経路が存在しない場合、距離は $\infty$ とします。
$T$ 個のテストケースが与えられるので、それぞれについて解いてください。
0,1 からなる文字列0入力は以下の形式で標準入力から与えられます。
$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$
ただし、 $case_i$ は $i$ 個目のテストケースを表し、以下の形式で与えられます。
$N$ $S_1$ $S_2$ $\ldots$ $S_N$
$T$ 個のテストケースそれぞれについて、順番に以下のように出力してください。
条件を満たすグラフが存在しない場合は -1 を $1$ 行に出力してください。
条件を満たすグラフが存在する場合は、グラフの辺の数を $M$ とし、$M$ 本の辺を任意の順番で出力してください。$i$ 番目に出力する辺の端点を $u_i,v_i$ として、以下の形式で出力してください。
$M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
なお、条件を満たすグラフが複数存在する場合は、どれを出力しても正解とみなされます。 出力が大きくなることがあるため、実行時間制限には十分注意してください。
4 3 010 000 000 3 000 000 000 3 010 101 010 7 0101010 1001000 0100000 0000010 1010000 1000000 0001000
2 1 3 2 3 0 -1 10 1 3 1 7 2 5 2 6 2 7 3 4 3 6 3 7 4 5 5 7
$1$ つ目のテストケースについて、頂点 $1$ と頂点 $2$ の距離は $2$ であるため、条件を満たします。
$2$ つ目のテストケースについて、辺を持たないグラフは条件を満たします。
$3$ つ目のテストケースについて、条件を満たすグラフは存在しないので -1 を出力してください。