퀸과 두 킹

100 x 100 크기의 체스판에 흰 퀸 하나와 검은 킹 두 개가 놓여 있다. 흰색과 검은색은 번갈아 이동하며, 흰 퀸이 먼저 이동한다. 검은색의 차례에는 두 검은 킹 중 정확히 하나만 이동한다.

목표는 흰 퀸이 두 검은 킹 중 하나가 있는 칸으로 이동해 그 킹을 잡는 것이다. 검은색은 잡히는 시점을 최대한 늦추려 한다. 킹은 퀸을 잡을 수 없고, 퀸이 있는 칸으로 이동할 수 없다.

킹은 상하좌우와 대각선 8방향 중 한 방향으로 한 칸 이동한다. 퀸은 같은 8방향 중 한 방향으로 원하는 칸 수만큼 이동한다. 양쪽 모두 자기 차례를 건너뛸 수 없고, 체스판 밖으로 이동할 수 없다. 주어진 초기 배치에서 킹 하나를 잡기 위해 필요한 퀸 이동 횟수의 최솟값을 구하라.

첫째 줄에는 퀸의 위치가, 둘째 줄과 셋째 줄에는 두 킹의 위치가 주어진다.

각 위치는 행 열 형식이다. 가장 왼쪽 위 칸은 (0, 0), 가장 오른쪽 아래 칸은 (99, 99)이다. 처음에 퀸과 킹이 같은 칸에 있거나 두 킹이 같은 칸에 있는 경우는 없다.

킹 하나를 잡기 위해 필요한 퀸 이동 횟수의 최솟값을 출력한다.