HZNUOJ

FIND WAY OUT!

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:14     AC:1     Score:99.83

Description

小马哥最近沉迷steam上的一款名叫wayout的游戏

WayOut 是一个按灯的游戏,每按一盏灯会改变它及周围所有灯的状态(不包含斜对角),目标是把所有灯关掉。

现在给定一个地图,问是否存在一种解法,能够将所有灯关掉。如果存在,输出解法,反之输出-1

Input

第一行一个数字T代表有T组数据

每组数据第一行一个数n,表示该组数据有n盏灯

接下来n行,每行三个数字x,y,z,代表在坐标(x,y)的位置上有一盏灯且灯的状态为z

z只可能为0或1,其中0代表关,1代表开

1<=T<=10

1<=x,y<=10

0<=n<=100

Output

对于每组数据如果存在解法则输出一个m,接下来m行每行有两个数字x,y,代表按下(x,y)坐标上的灯

如果无解则只输出一行-1,m不能大于1000

Samples

input
1 9 1 1 0 1 2 1 1 3 0 2 1 1 2 2 0 2 3 1 3 1 0 3 2 1 3 3 0
output
4 1 2 2 1 2 3 3 2

Hint

没有灯的时候答案是0

Author

LI, Heng