33617번 - 치터 잡기 스페셜 저지

문제

가로의 길이와 세로의 길이가 $N$인 격자판 위에 치터 한 명이 있다. 피갤컵의 매니저인 당신은 이 치터를 잡으려고 하지만, 치터가 어디에 있는지는 모른다. 당신은 다음과 같은 규칙을 통해 치터를 잡기로 했다. 맨 처음에, 당신은 시작할 위치를 결정한다. 그 뒤 1ドル$초가 지날 때마다 다음과 같은 방법으로 이동한다:

1. 당신은 최대 $N$번 인접한 칸으로 이동한다. 어떤 칸이 다른 칸과 인접하다는 것은, 두 칸이 하나의 변을 맞대고 있는 것을 의미한다. 만약 당신이 이동하는 경로에 치터가 있다면, 당신은 치터를 잡게 된다.
2. 만약 1번 과정에서 치터가 잡히지 않았다면, 치터는 자신과 인접한 임의의 칸으로 이동한다. 만약 치터가 당신이 있는 칸으로 이동한다면 당신은 치터를 잡게 된다.

각 과정에서 당신과 치터가 이동하여 도착한 마지막 칸이 각각 다음 과정의 시작 칸이 된다.

초기에 치터가 당신과 같은 위치에 있다면, 당신은 위의 과정을 거치지 않고 치터를 바로 잡을 수 있을 것이다. 따라서 치터의 초기 위치는 당신의 초기 위치와 다르다고 가정해도 좋다.

당신은 치터가 어디에 있는지와 치터가 어떻게 이동하는지 모르기 때문에, 가능한 치터의 모든 위치와 움직임에 대해 치터를 잡을 수 있도록 이동해야 한다. 치터를 잡는데에 그렇게 오랜 시간을 투자하고 싶지 않기 때문에, 당신은 $N^2$초 내로 치터를 잡아야 한다. 당신의 초기 위치와 이동할 경로를 출력하라.

입력

첫째 줄에 양의 정수 $N$이 주어진다. $(2\le N\le 50)$

출력

첫째 줄에 필요한 시간을 나타내는 정수 $t$를 출력한다. $(1\le t\le N^2)$

둘째 줄에 시작할 위치를 나타내는 두 정수 $x, y$를 공백을 두고 출력한다. 시작할 위치가 $x$행 $y$열임을 나타낸다.

다음 $t$개의 줄에 걸쳐 당신이 할 이동을 출력한다. $i+2$번째 줄에 이동횟수를 나타내는 정수 $m_i$와 이동할 칸을 나타내는 2ドルm_i$개의 정수 $x_{i1}, y_{i1}, x_{i2}, y_{i2}, \dots, x_{im_i}, y_{im_i}$를 공백을 두고 출력한다. 이는 $i$초에 이동할 횟수가 $m_i$번임을 나타내고 $i$초에 $j$번째로 이동할 칸이 $x_{ij}$행 $y_{ij}$열임을 나타낸다. $(1\le m_i\le N)$

제한

힌트