9021번 - 숫자 퍼즐 스페셜 저지다국어

숫자 퍼즐은 표시된 수들을 잇는 통로를 찾는 퍼즐이다. 참가자는 표의 모든 똑같은 숫자끼리 이을 수 있는, 끊기지 않는 선을 찾아야 한다. 선들은 여러 갈래로 나눠지거나 교차할 수 없다. 그리고 숫자는 각 선의 양 끝에 있어야 한다.

그리고 선들은 모든 칸을 정확히 한 번씩만 지나야 한다.

우리는 여기에서 한 숫자는 한 쌍만 있다는 것을 알 수 있다. 그리고 표의 크기가 m x n 인 경우에, m과 n은 모두 짝수이다. 다음 그림을 보자.

상근이는 이 1 두 개가 놓여져 있는 표에서 이 퍼즐을 완성하려고 한다. 상근이를 도와 문제의 조건을 지키는 길을 찾는 프로그램을 만드시오.

입력의 첫 줄은 T (테스트 케이스의 수)로 이루어져 있다.

각 테스트 케이스는 표의 행의 개수 m, 열의 개수 n (2 ≤ m, n ≤ 100)이 첫 줄에 주어진다. 두 번째 줄과 세 번째 줄은 i와 j, a와 b(각 1의 위치를 나타내는 좌표)로 이루어져 있다.

각 테스트 케이스별로 가는 길이 없으면 -1을 출력한다. 아니면, 1을 출력한 다음 m x n 줄마다 순서대로 길이 지나는 좌표를 출력한다. 양 끝 줄에는 각 1의 위치를 출력해야 한다.