Navigation 2

JOI Kingdom은 바다로 둘러싸인 섬이다. JOI Kingdom의 땅은 N행 N열의 정사각형 칸으로 이루어진 격자이다. 세로 방향이 남북 방향이고, 가로 방향이 서동 방향이다. 북쪽에서 (r + 1)번째 행(0 ≤ r ≤ N − 1)과 서쪽에서 (c + 1)번째 열(0 ≤ c ≤ N − 1)에 있는 칸을 칸 (r, c)로 표기한다.

JOI Kingdom의 여왕 Anna는 Bruno를 파티에 초대하려고 한다. Anna는 지금 파티 장소를 고르고 있다. Anna는 이미 파티 장소의 후보 칸 K (= 7)개를 골랐다. 후보 칸에는 0부터 K − 1까지 번호가 붙어 있다. 후보 칸 i는 칸 (Ri, Ci)이다. 어떤 후보 칸도 바다에 인접하지 않는다.

파티 장소는 파티 당일에 정해진다.

파티 전날, Bruno가 길을 잃지 않고 파티 장소에 도착할 수 있도록 Anna는 모든 칸에 깃발을 꽂는다. Anna는 각 깃발에 1 이상 1 000 000 000 이하의 정수를 하나씩 적는다.

파티 당일, Bruno에게는 후보 칸의 번호 t (0 ≤ t ≤ K − 1)만 알려진다. 그 후 Bruno는 헬리콥터를 타고 바다에 인접하지 않은 칸에 도착한다. 그리고 파티 장소를 향해 이동을 시작한다.

Bruno는 자신이 어디에 있는지 모르지만, 동서남북 방향은 알고 있다. Bruno는 현재 칸과 그 주위 8칸에 있는 깃발만 볼 수 있다. 즉, Bruno가 칸 (a, b) (1 ≤ a ≤ N − 2, 1 ≤ b ≤ N − 2)에 있을 때 볼 수 있는 깃발은 다음 9개 칸에 있는 것뿐이다:

(a − 1, b − 1), (a − 1, b), (a − 1, b + 1), (a, b − 1), (a, b), (a, b + 1), (a + 1, b − 1), (a + 1, b), (a + 1, b + 1)

Bruno는 다음 5가지 행동 중 하나를 할 수 있다.

• 행동 0: Bruno가 동쪽으로 한 칸 이동한다. 즉, 칸 (a, b)에서 칸 (a, b + 1)로 이동한다.
• 행동 1: Bruno가 서쪽으로 한 칸 이동한다. 즉, 칸 (a, b)에서 칸 (a, b − 1)로 이동한다.
• 행동 2: Bruno가 남쪽으로 한 칸 이동한다. 즉, 칸 (a, b)에서 칸 (a + 1, b)로 이동한다.
• 행동 3: Bruno가 북쪽으로 한 칸 이동한다. 즉, 칸 (a, b)에서 칸 (a − 1, b)로 이동한다.
• 행동 4: Bruno가 파티가 현재 칸에서 열린다고 생각하고 그 자리에 머문다. 이동을 멈춘다.

파티에 늦게 도착하는 것은 금지되어 있으므로, Bruno는 행동 횟수가 최소가 되도록 파티 장소로 이동해야 한다. 따라서 이 문제의 설정상 Bruno는 바다에 인접한 칸에 절대 들어가지 않는다.

깃발에 큰 정수를 적는 것은 번거로운 일이므로, Anna는 깃발에 적힌 정수 중 최댓값을 최소화하려고 한다.

Anna의 전략과 Bruno의 전략을 구현하는 프로그램을 작성하라. Anna는 깃발에 정수를 적고, Bruno는 최소 횟수의 행동으로 파티 장소에 도착해야 한다.

샘플 채점기는 다음 데이터를 표준 입력에서 읽는다. 주어지는 값은 모두 정수이다.

Q
(시나리오 0에 대한 입력)
.
.
.
(시나리오 Q − 1에 대한 입력)

각 시나리오에 대한 입력은 다음과 같다.

N K
R0 C0
.
.
.
RK−1 CK−1
a b

샘플 채점기의 입력으로 N은 3 ≤ N ≤ 100 범위, K는 1 ≤ K ≤ 7 범위로 설정할 수 있다. 이 범위는 이 문제의 실제 제약과 다르다.

프로그램이 정상적으로 종료되면 샘플 채점기는 다음 정보를 표준 출력에 쓴다(명확성을 위해 따옴표를 붙였다).

• 답이 맞으면 함수 Anna가 깃발에 적은 정수 중 최댓값을 “Accepted : Maximum value = 12” 형식으로 쓴다.
• 프로그램이 Wrong Answer로 판정되면 그 종류를 “Wrong Answer [1]” 형식으로 쓴다.

프로그램이 여러 종류의 Wrong Answer로 판정되면 샘플 채점기는 그중 하나만 보고한다.

• 1 ≤ Q ≤ 300.
• 5 ≤ N ≤ 100.
• K = 7.
• 1 ≤ Ri ≤ N − 2 (0 ≤ i ≤ K − 1).
• 1 ≤ Ci ≤ N − 2 (0 ≤ i ≤ K − 1).
• (Ri, Ci) ≠ (Rj, Cj) (0 ≤ i < j ≤ K − 1).
• 1 ≤ a ≤ N − 2.
• 1 ≤ b ≤ N − 2.