Untitled

public class Solution {
	static int[][] map;
	static PointCs[] dirtys;
	static int MAX_DIRTY = 12;
	static int totalDirty = 0;
	static Queue<PointCs> qt;
	static int[] visited;
	static int[][] step;
	static int[][] adj;

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {	
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int n = sc.nextInt();
			int m = sc.nextInt();

			int xR = 0, yR = 0;

			totalDirty = 0;
			qt = new Queue<Solution.PointCs>();

			map = new int[n][m];
			step = new int[n][m];

			dirtys = new PointCs[MAX_DIRTY];
			visited = new int[MAX_DIRTY];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 1) {
						totalDirty++;
						dirtys[totalDirty] = new PointCs(i, j);
					} else if (map[i][j] == 3) {
						xR = i;
						yR = j;
					}
				}
			}

			adj = new int[totalDirty + 1][totalDirty + 1];
			bfs(xR, yR);

			boolean canNotGoDirty = false;
			PointCs diryCs;
			for (int i = 1; i <= totalDirty; i++) {
				for (int j = i + 1; j <= totalDirty; j++) {
					if (step[i][j] != 0) {
						adj[i][j] = step[i][j] - 1;
						adj[j][i] = step[i][j] - 1;
					} else {
						adj[i][j] = step[i][j] - 1;
						adj[j][i] = step[i][j] - 1;
						canNotGoDirty = true;
					}
				}
			}

			if (canNotGoDirty) {
				System.out.println(-1);
			} else {

			}

//			for (int i = 0; i < step.length; i++) {
//				System.out.println(Arrays.toString(step[i]));
//			}
//			System.out.println();

			dirtys = null;
			adj = step = map = null;
			visited = null;
			qt = null;
		}
		sc.close();
	}

	private static void bfs(int x, int y) {
		qt.reset();
		qt.enQueue(new PointCs(x, y));
		step[x][y] = 1;

		PointCs tmpPoint;
		while (!qt.isEmpty()) {
			tmpPoint = qt.peek();
			qt.deQueue();

			for (int i = 0; i < 4; i++) {
				int xx = tmpPoint.x + dx[i];
				int yy = tmpPoint.y + dy[i];
				if (isSafe(xx, yy)) {
					if (step[xx][yy] == 0) {
						step[xx][yy] = step[tmpPoint.x][tmpPoint.y] + 1;
						qt.enQueue(new PointCs(xx, yy));
					}
				}
			}
		}

		int robot = 0;
		PointCs dirtyCs;
		for (int i = 1; i <= totalDirty; i++) {
			dirtyCs = dirtys[i];
			if (step[dirtyCs.x][dirtyCs.y] != 0) {
				adj[robot][i] = step[dirtyCs.x][dirtyCs.y] - 1;
				adj[i][robot] = step[dirtyCs.x][dirtyCs.y] - 1;
			} else {
				adj[robot][i] = -1;
				adj[i][robot] = -1;
			}
		}

		for (int i = 0; i < step.length; i++) {
			System.out.println(Arrays.toString(step[i]));
		}
		System.out.println();

		for (int i = 0; i < adj.length; i++) {
			System.out.println(Arrays.toString(adj[i]));
		}
		System.out.println();
	}

	private static boolean isSafe(int xx, int yy) {
		if (xx >= 0 && xx < map.length && yy >= 0 && yy < map[0].length) {
			if (map[xx][yy] != 2) {
				return true;
			}
		}

		return false;
	}