시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 266 47 31 19.018%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

2
4 4
2 2
3 3
6 6
3 4
4 4

예제 출력

-1
1
4 4
5 4
5 5
4 5
3 5
2 5
1 5
1 6
2 6
3 6
4 6
5 6
6 6
6 5
6 4
6 3
6 2
6 1
5 1
4 1
3 1
2 1
1 1
1 2
2 2
3 2
4 2
5 2
5 3
4 3
3 3
2 3
1 3
1 4
2 4
3 4

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2011 F번

비슷한 문제