Testify

Darkest night, I'll confront you here....

이 문제는 투 스텝 인터랙티브 문제입니다.

히카리와 타이리츠는 협동 게임을 하여 그들의 우정을 증명하고자 한다.

게임은 $n$개의 직선이 있는 평면에서 진행된다. 어떠한 두 직선도 평행하지 않으며, 어떠한 세 직선도 한 점에서 만나지 않으며, 모든 직선은 $x$축, 혹은 $y$축과 평행하지 않는다.

어떠한 위치 $(x_0, y_0)$ 이 직선 $y = ax + b$ 위에 있다는 것은, $y_0>ax_0+b$를 만족한다는 것이다. 반대로, 어떠한 위치 $(x_0,y_0)$ 이 직선 $y = ax + b$ 아래에 있다는 것은, $y_0<ax_0+b$를 만족한다는 것이다. 이에 따라, 평면 상에서 직선에 속하지 않는 모든 점들은 각 직선의 위에 있거나 아래에 있다.

어떠한 두 점 $p, q$ 가 $n$ 개의 직선에 대해서 항상 같이 위에 있거나 같이 아래에 있다면, 두 점 $p, q$ 는 같은 구역에 속한다고 한다. 상술한 문제 조건에 따라서, 평면은 정확히 $\frac{n(n+1)}{2}+1$ 개의 구역들로 분할됨을 증명할 수 있다.

두 서로 다른 구역 $e, f$ 가 인접하다는 것은, $e, f$ 에 속하는 임의의 두 점 $p(e), p(f)$ 에 대해서 $p(e)$ 와 $p(f)$ 사이를 정확히 하나의 직선만을 가로질러 이동할 수 있음을 뜻한다. 서로 다른 인접한 쌍은 정확히 $n^2$ 개임을 증명할 수 있다.

게임은 히카리가 각 구역들에 특정한 표시를 남긴 후, 타이리츠가 이 표시를 통해서 구역 간을 이동하는 식으로 이루어진다.

히카리의 차례를 먼저 설명한다. 히카리가 각 구역들에 표시를 남기는 것은 다음과 같은 인터랙션을 통해 이루어진다.

히카리는 $1\,000$ 이하의 양의 정수 $M$을 선언한다.
채점 인터랙터는 다음과 같은 정보들을 히카리에게 표준 입력으로 전달한다:
1. 양의 정수 $n$.
2. 평면 상의 $n$ 개의 직선의 정보.
3. 평면 상의 모든 $\frac{n(n+1)}{2}+1$ 개의 구역 각각에 대해, 길이 $n$ 의 이진 문자열이 주어진다. 각 구역은 주어진 순서대로 $1$ 에서 $\frac{n(n+1)}{2}+1$ 까지의 서로 다른 번호가 부여된다. $i$ 번 구역을 나타내는 문자열의 $j$ 번 문자는, $i$번 구역이 $j$번 직선의 아래에 있다면 $0$이고, 위에 있다면 $1$ 이다.
4. 총 $n^2$개의 인접한 두 구역의 번호 쌍이 주어진다.
히카리는 각 구역마다 두 개의 정수를 표시해야 한다. 첫 번째 정수는 $1$부터 $M$ 사이의 정수여야 하며, 두 번째 정수는 $0$부터 $n$ 사이의 정수여야 한다.

이제 타이리츠의 차례를 설명한다. 타이리츠의 목표는 평면의 어떤 구역에서 게임을 시작하여, 다른 어떤 구역으로 이동해야 한다. 일련의 이동 과정은 다음과 같은 인터랙션을 통해 이루어진다.

채점 인터랙터는 첫 줄에 히카리가 받은 직선의 개수 $n$ 을 표준 입력으로 전달한다.
채점 인터랙터는 다음 줄에 총 $4$ 개의 정수를 타이리츠에게 표준 입력으로 전달한다.
1. 첫 번째와 두 번째 정수는, 타이리츠가 현재 위치한 구역에 히카리가 표시한 두 정수 쌍이다. 두 정수의 순서는 히카리가 부여한 그대로이다.
2. 세 번째와 네 번째 정수는, 타이리츠가 도착해야 하는 구역에 히카리가 표시한 두 정수 쌍이다. 두 정수의 순서는 히카리가 부여한 그대로이다.
타이리츠는 자신이 있는 구역과 인접한 구역으로 이동할 수 있다. 이때, 어떤 두 구역이 인접하다는 것은 두 구역이 공유하는 변이 존재한다는 것이다. 타이리츠가 자신과 인접한 구역으로 이동하는 것은 다음과 같은 절차를 $6n$ 번 반복하여 이루어진다.
1. 채점 인터랙터는 길이 $M$의 이진수열을 타이리츠에게 표준 입력으로 전달한다. 해당 이진수열의 $i$번째 원소가 $0$이라면 직전에 방문하지 않은 구역들 중 $i$를 첫번째 정수로 가지는 인접한 구역이 없다는 것이고, $1$이라면 있다는 것이다.
2. 타이리츠는 둘 중 하나의 행동을 할 수 있다:
  1. 어떤 $x(1\le x\le M)$를 골라서, 자신과 인접하고 직전에 방문하지 않았으며 첫 번째 정수가 $x$인 구역으로 이동한다. 만약 직전에 방문하지 않았으며 첫 번째 정수가 $x$인 구역이 여러 개라면, 그중 임의의 한 구역으로 이동한다.
  2. 이전에 방문했던 구역으로 돌아간다.
3. 채점 인터랙터는 타이리츠가 도착지에 도달했는지 여부를 타이리츠에게 알려준다. 타이리츠가 도착지에 도달하였다면, 프로그램은 즉시 종료하여야 한다. 프로그램이 종료되면 게임은 성공한다. 도달하지 못 했고, 이동 횟수가 $6n$ 번 미만일 경우, 다시 이동을 시작한다.
타이리츠가 $6n$ 번의 이동 후에도 도착지에 도달하지 못 했다면 게임은 실패한다.

타이리츠의 차례를 진행할 때, 타이리츠가 도착하고 싶은 구역과 첫 번째 정수와 두 번째 정수가 동일한 어떤 구역에 도달했다고 하더라도, 해당 구역이 타이리츠가 도착하고 싶은 구역은 아닐 수도 있음에 유의하라.

게임을 성공할 수 있게, 히카리와 타이리츠의 전략을 수행하는 프로그램을 작성하여라. 히카리가 처음에 선언하는 정수 $M$이 작으면 작을수록 더욱 큰 점수를 얻을 수 있다.

문제

제한

힌트