꿀 도둑

한 변의 길이가 R인 육각형 벌집의 인접 관계를 만들고 밀랍 칸을 제거한 뒤 A에서 B까지 캐야 하는 칸 수의 최솟값을 구해 N과 비교한다.

보통6그래프BFS구현기하면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

정찰개미 0x67이 먹이를 찾다가 근처에서 벌집을 발견했다. 벌집 안쪽에는 굳은 꿀이 들어 있는 방이 있고, 그 꿀을 집으로 옮기면 겨울을 날 수 있다. 꿀이 있는 방까지 가려면 벌집의 방을 갉아서 통로를 뚫어야 한다.

벌집은 한 변이 RR개의 방으로 이루어진 정육각형이고, 방은 모두 R3(R1)3R^3 - (R-1)^3개다. 방 번호는 행 우선 순서로 붙는다. 위쪽 행부터 차례로, 한 행 안에서는 왼쪽부터 오른쪽으로 번호를 붙인다. 벽 하나를 맞대고 있는 두 방은 서로 인접하다. R=4R = 4인 벌집의 번호는 다음과 같다.

R = 4인 벌집의 방 번호

0x67은 구멍으로 들어가 AA번 방에 도착한다. 들어가는 방은 갉지 않는다. 그다음부터는 인접한 방을 하나씩 갉으면서 꿀이 있는 BB번 방으로 향한다. 턱의 힘에 한계가 있어서 갉을 수 있는 방은 최대 NN개다. 일부 방은 밀랍으로 굳어 있어 갉을 수 없으므로, 그런 방은 피해서 돌아가야 한다.

0x67은 갉기 전에 BB번 방에 닿는 데 필요한 방의 최소 개수 KK를 먼저 계산한다. 즉 BB는 갉는 순서로 KK번째 방이다. K>NK > N이면 통로를 뚫을 만큼 힘이 세지 않다.

입력

첫째 줄에 정수 다섯 개 RR, NN, AA, BB, XX가 공백으로 구분되어 주어진다.

  • RR: 벌집 한 변의 방 개수 (2R202 \le R \le 20). 벌집 전체의 방은 R3(R1)3R^3 - (R-1)^3개다.
  • NN: 0x67이 갉을 수 있는 방의 최대 개수 (1N<R3(R1)31 \le N < R^3 - (R-1)^3).
  • AA: 0x67이 들어가는 방의 번호. 이 방은 벌집 가장자리에 있어서 인접한 방이 여섯 개보다 적다.
  • BB: 꿀이 있는 방의 번호 (1BR3(R1)31 \le B \le R^3 - (R-1)^3).
  • XX: 밀랍으로 굳은 방의 개수 (0X<(R3(R1)3)10 \le X < (R^3 - (R-1)^3) - 1).

둘째 줄에 밀랍으로 굳은 방의 번호 XX개가 공백으로 구분되어 주어진다. X=0X = 0이면 둘째 줄은 비어 있다.

AA, BB, 둘째 줄의 번호는 모두 서로 다르고, 각각 11 이상 R3(R1)3R^3 - (R-1)^3 이하의 정수다.

출력

0x67이 꿀에 닿을 수 있으면 갉아야 하는 방의 최소 개수 KK를 출력한다. 밀랍에 막혀 BB번 방에 닿을 수 없거나 K>NK > N이면 대신 No를 출력한다.

힌트

첫 번째 예제, K = 6

첫 번째 예제의 벌집이다. 검은 방은 밀랍으로 굳은 방이고, 초록색 방 여섯 개가 0x67이 갉는 방이다.

두 번째 예제, No

두 번째 예제는 벌집이 같고 N=3N = 3이다. 빨간 방 세 개를 갉고 나면 턱이 버티지 못하므로 꿀에 닿지 못한다.