숫자 연결 퍼즐

숫자가 적힌 격자에서 같은 숫자 두 칸을 하나의 선으로 이어야 한다. 이 문제에서는 숫자 1이 적힌 칸이 정확히 두 개만 주어진다.

선은 상하좌우로 인접한 칸 사이를 지나며, 끊기거나 갈라지거나 서로 교차할 수 없다. 두 개의 1은 선의 양 끝이어야 하고, 선은 격자의 모든 칸을 정확히 한 번씩 지나야 한다.

행의 수 m과 열의 수 n은 모두 짝수이며, 2 ≤ m, n ≤ 8이다. 두 1의 위치가 주어졌을 때 조건을 만족하는 경로를 찾아라.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 격자의 행 수 m과 열 수 n이 주어진다. 다음 두 줄에는 두 1의 위치 (i, j)와 (a, b)가 각각 주어진다. 모든 좌표는 1부터 시작한다.

각 테스트 케이스마다 조건을 만족하는 경로가 없으면 -1을 출력한다.

경로가 있으면 먼저 1을 출력하고, 이어서 경로가 지나는 m × n개의 좌표를 순서대로 한 줄에 하나씩 출력한다. 첫 좌표와 마지막 좌표는 주어진 두 1의 위치여야 한다.