cho.sh

토러스

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

정다각형은 모든 변의 길이가 같고 모든 내각의 크기가 같은 다각형이다. 유클리드 평면의 정규 타일링은 합동인 정다각형을 서로 겹치지 않게, 꼭짓점이 꼭짓점과 맞닿도록 놓아 평면 전체를 덮는 것이다. 정규 타일링이 가능한 정다각형은 정사각형, 정삼각형, 정육각형 세 가지뿐이다. 격자는 평면에 그렸을 때 정규 타일링이 되는 무한 그래프이며, 따라서 사각 격자, 삼각 격자, 육각 격자가 있다.

이런 격자는 원래의 대칭 구조를 유지한 채 정점과 간선의 개수가 유한한 그래프로 바꿀 수 있다. 그렇게 얻은 유한 그래프는 토러스 표면에 간선이 서로 교차하지 않게 그릴 수 있고, 길이가 가장 짧은 사이클이 둘러싸는 영역의 모양과 크기도 서로 비슷하다. 이런 그래프를 토로이달 격자라 하고, 정의는 다음과 같다.

정의 1. m≥3m \ge 3, n≥3n \ge 3인 정수 mm, nn이 주어졌을 때, m×nm \times n 사각 토로이달 격자의 정점 집합은 {vi,j:0≤i≤m−1, 0≤j≤n−1}\{v_{i,j} : 0 \le i \le m-1,\ 0 \le j \le n-1\}이다. 두 정점 vi,jv_{i,j}와 vi′,j′v_{i',j'}는 다음 두 조건 중 하나를 만족할 때 간선으로 이어진다.

  • i′=ii' = i이고 j′≡j+1(modn)j' \equiv j+1 \pmod{n}
  • j′=jj' = j이고 i′≡i+1(modm)i' \equiv i+1 \pmod{m}

정의 2. m≥3m \ge 3, n≥3n \ge 3이고 mm이 짝수인 정수 mm, nn이 주어졌을 때, m×nm \times n 삼각 토로이달 격자는 같은 크기의 사각 토로이달 격자에 다음 간선을 모두 추가한 그래프이다. 모든 ii, jj에 대해,

  • ii가 짝수이면 vi,jv_{i,j}와 vi′,j′v_{i',j'}를 잇는다. 여기서 i′≡i+1(modm)i' \equiv i+1 \pmod{m}이고 j′≡j−1(modn)j' \equiv j-1 \pmod{n}이다.
  • ii가 홀수이면 vi,jv_{i,j}와 vi′,j′v_{i',j'}를 잇는다. 여기서 i′≡i+1(modm)i' \equiv i+1 \pmod{m}이고 j′≡j+1(modn)j' \equiv j+1 \pmod{n}이다.

정의 3. m≥4m \ge 4, n≥4n \ge 4이고 mm과 nn이 모두 짝수인 정수 mm, nn이 주어졌을 때, m×nm \times n 육각 토로이달 격자의 정점 집합은 {vi,j:0≤i≤m−1, 0≤j≤n−1}\{v_{i,j} : 0 \le i \le m-1,\ 0 \le j \le n-1\}이다. 두 정점 vi,jv_{i,j}와 vi′,j′v_{i',j'}는 다음 두 조건 중 하나를 만족할 때 간선으로 이어진다.

  • j′=jj' = j이고 i′≡i+1(modm)i' \equiv i+1 \pmod{m}
  • i′=ii' = i이고 j′≡j+1(modn)j' \equiv j+1 \pmod{n}이고 i+j≡0(mod2)i+j \equiv 0 \pmod{2}

격자 그래프 알고리즘 라이브러리를 만드는 프로젝트를 돕기 위해, 주어진 m×nm \times n 토로이달 격자에서 모든 정점을 정확히 한 번씩 지나는 사이클을 찾는 프로그램을 작성한다. 사이클은 서로 다른 정점 mnmn개의 수열 (u1,u2,…,umn)(u_1, u_2, \dots, u_{mn})으로, k∈{1,…,mn−1}k \in \{1, \dots, mn-1\}인 모든 kk에서 uku_k와 uk+1u_{k+1}이 인접하고 umnu_{mn}과 u1u_1도 인접한 것을 말한다. 사각 토로이달 격자는 비교적 단순하므로 삼각 토로이달 격자와 육각 토로이달 격자만 다룬다.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. TT는 양의 정수이다. 이어지는 TT개의 줄에는 각각 세 정수 mm, nn, pp가 공백으로 구분되어 주어진다. 3≤m≤1113 \le m \le 111, 3≤n≤1113 \le n \le 111이고 p∈{3,6}p \in \{3, 6\}이다. p=3p = 3이면 해당 그래프는 m×nm \times n 삼각 토로이달 격자이고, p=6p = 6이면 m×nm \times n 육각 토로이달 격자이다.

입력으로 주어지는 격자는 항상 정의를 만족한다. 즉 p=3p = 3이면 mm이 짝수이고, p=6p = 6이면 mm과 nn이 모두 짝수이며 4 이상이다.

출력

테스트 케이스마다 입력에 주어진 순서대로 결과를 출력한다. 각 테스트 케이스의 첫 줄에는 사이클이 존재하는지를 나타내는 정수를 출력한다. 존재하면 1, 존재하지 않으면 -1이다. 첫 줄이 1인 경우에만 이어서 mnmn개의 줄에 사이클을 이루는 정점을 순서대로 출력한다. 정점 vi,jv_{i,j}는 (i,j) 꼴로 출력하고, 한 줄 안에는 공백이나 탭을 넣지 않는다.

사이클은 여러 개일 수 있으므로, 다음 규칙으로 만든 사이클만 정답으로 인정한다. 아래에서 a mod ba \bmod b는 00 이상 bb 미만인 나머지를 뜻한다.

p=3p = 3이면 다음 순서로 출력한다.

  1. v0,0v_{0,0}
  2. j=0,1,…,n−1j = 0, 1, \dots, n-1 순서로, jj가 짝수이면 v1,j,v2,j,…,vm−1,jv_{1,j}, v_{2,j}, \dots, v_{m-1,j}를, jj가 홀수이면 vm−1,j,vm−2,j,…,v1,jv_{m-1,j}, v_{m-2,j}, \dots, v_{1,j}를 출력한다.
  3. v0,n−1v_{0,n-1}
  4. v0,n−2,v0,n−3,…,v0,1v_{0,n-2}, v_{0,n-3}, \dots, v_{0,1}

p=6p = 6이면 k=0,1,…,n/2−1k = 0, 1, \dots, n/2-1 순서로 다음 2m2m개의 정점을 출력한다.

  1. t=0,1,…,m−1t = 0, 1, \dots, m-1 순서로 v(1−t) mod m, 2kv_{(1-t) \bmod m,\ 2k}
  2. t=0,1,…,m−1t = 0, 1, \dots, m-1 순서로 v(2+t) mod m, 2k+1v_{(2+t) \bmod m,\ 2k+1}

이 규칙은 제약을 만족하는 모든 입력에서 사이클을 만들어내므로, 각 테스트 케이스의 첫 줄은 항상 1이다.