고장 난 방향 지시등

최근 차량에 소프트웨어 업데이트가 적용되었다. 이제 방향 지시등을 너무 많이 켜면 차량이 "buffer overflow"라는 메시지를 띄우며 꺼진다. 그 말이 무슨 뜻인지는 모르겠지만, 좋은 소식도 있다. 이제 고장 난 자동차 보존 컨벤션(BAPC)에 초대받았다.

늦게 알았으니 최대한 빨리 그곳까지 운전해서 가야 한다. 물론 교통 규칙은 모두 지켜야 한다. 교차로마다 그 교차로가 모든 방향으로 도로가 있는지와 상관없이 다음 규칙을 따라야 한다.

• 교차로에서 좌회전(또는 우회전)할 때는 왼쪽(또는 오른쪽) 방향 지시등을 켜야 한다.
• 직진할 때는 방향 지시등을 꺼야 한다.
• 유턴은 허용되지 않는다. 즉, 온 길을 되돌아갈 수 없다.

방향 지시등을 안전하게 쓰기 위해 점등 횟수를 최대 $k$번으로 제한하기로 한다. 방향 지시등은 언제든지 끌 수 있다. 제약이 빡빡해 보이지만 한 가지 영리한 점이 있다. 방향 지시등을 켜 둔 상태(자동으로 꺼지지 않는 동안)에는 같은 방향으로 계속 회전할 수 있다.

도로망은 교차로와 교차로 사이를 잇는 도로로 이루어진다. 도로는 항상 북, 동, 남, 서 중 한 방향에서 시작해서 한 방향으로 끝난다. 또한 같은 교차로에서 시작해서 같은 교차로에서 끝나는 도로는 없다. 예로 그림 B.1에 나타낸 예제 1번부터 3번까지를 보자. 이 예제들은 $k$ 값만 다르다.

그림 B.1: 첫 번째, 두 번째, 세 번째 예제 입력의 시각화.

길 찾기를 단순하게 하기 위해 모든 도로는 같은 시간에 지날 수 있다고 가정한다. 즉, 각 도로의 길이는 $1$이다. 현재 위치에서 BAPC까지 가는 가장 짧은 경로를 구하라. 이때 방향 지시등을 $k$번보다 많이 켜서는 안 된다. 현재 위치에서는 방향 지시등을 쓰지 않고 어느 방향으로든 운전할 수 있다.

입력은 다음과 같다.

• 첫 줄에 두 정수 $n$과 $k$($1 \le n \le 5000$, $0 \le k \le 20$)가 주어진다. 각각 교차로의 개수와 방향 지시등을 켤 수 있는 횟수이다.
• 다음 $n$개 줄의 $i$번째 줄에는 네 정수 $v_i^{\text{N}}$, $v_i^{\text{E}}$, $v_i^{\text{S}}$, $v_i^{\text{W}}$($0 \le v_i^{\text{N}}, v_i^{\text{E}}, v_i^{\text{S}}, v_i^{\text{W}} \le n$)가 주어진다. 이는 교차로 $i$에서 북, 동, 남, 서쪽 도로를 타고 도달할 수 있는 교차로 번호이며, 도로가 없으면 $0$이다.

출발지는 교차로 $1$이고, BAPC는 교차로 $n$에 있다. 각 교차로 $i$에서 다른 교차로 $j$로 가는 도로는 최대 한 개이다. 이 도로가 있으면 교차로 $j$에서 교차로 $i$로 가는 도로도 정확히 한 개 있다.

교차로 $1$에서 $n$까지 방향 지시등을 최대 $k$번만 켜고 갈 수 있다면, 그러한 경로 중 가장 짧은 경로의 길이를 출력한다. 그렇지 않으면 "impossible"을 출력한다.