현대모비스 자율 주행 테스팅 2

이 문제는 현대모비스 자율 주행 테스팅 1 문제와 입력 형식이 다릅니다. 이 문제의 코드로 현대모비스 자율 주행 테스팅 1 문제를 해결할 수는 없으니 주의하세요.

현대모비스는 모빌리티 플랫폼 프로바이더로서 SDV(Software Defined Vehicle) 시대를 이끌기 위해 자율주행, 전동화, 커넥티비티 등 여러 분야에서 SW 연구개발을 활발히 진행하고 있다. 특히 서산 주행 시험장에서는 자율 주행 자동차 개발을 위한 시범 주행이 한창이다.

샘플 주행 트랙은 모두 $M$종류이며, 각각 $1$번부터 $M$번까지 번호가 매겨져 있다. $i$번 샘플 주행 트랙은 $2$행 $N_i$열이며, 각 칸은 도로 또는 장애물이다. 시범 주행 트랙은 샘플 주행 트랙 $K$개를 차례로 이어 붙여 만든다. 시범 주행 트랙에 쓰인 샘플 주행 트랙의 번호를 차례로 $A_1, A_2, \cdots, A_K$라 하면, 시범 주행 트랙은 $2$행 $\sum_{i=1}^K N_{A_i}$열이 된다.

자동차는 다음 두 가지 방법으로 트랙 위를 이동할 수 있다.

• 차선 변경: 같은 열의 다른 행으로 이동한다. 즉 $1$행 $j$열에 있으면 $2$행 $j$열로, $2$행 $j$열에 있으면 $1$행 $j$열로 이동한다.
• 직진: 같은 행의 다음 열로 이동한다. 즉 $i$행 $j$열에 있으면 $i$행 $j+1$열로 이동한다.

두 경우 모두 도착하는 칸에 장애물이 있으면 안 된다.

시범 주행은 트랙의 첫 번째 열에서 시작하고, 마지막 열에 도달하면 끝난다. 시작 칸과 끝 칸은 자유롭게 정할 수 있지만, 둘 다 도로여야 한다. 자율 주행 자동차가 시범 주행 트랙을 완주할 수 있는지 판별하고, 완주할 수 있다면 완주에 필요한 최소 이동 횟수를 구하라.

첫째 줄에 샘플 주행 트랙의 종류 수 $M$과 샘플 주행 트랙을 이어 붙인 횟수 $K$가 공백으로 구분되어 주어진다. ($1 \le M, K \le 200\,000$)

둘째 줄에 시범 주행 트랙을 구성하는 샘플 주행 트랙의 번호 $A_1, A_2, \cdots, A_K$가 차례대로 공백으로 구분되어 주어진다. ($1 \le A_i \le M$)

셋째 줄부터 $2M$개의 줄에 걸쳐 $i$번 샘플 주행 트랙의 정보가 주어진다. $2i+1$번째 줄에는 $i$번 샘플 주행 트랙의 $1$행을 나타내는 길이 $N_i$의 문자열 $S_{i1}$이 주어진다. $2i+2$번째 줄에는 $2$행을 나타내는 길이 $N_i$의 문자열 $S_{i2}$가 주어진다. ($1 \le N_i \le 500\,000$)

모든 문자열은 . 또는 #으로만 이루어져 있다. .은 도로, #은 장애물을 뜻한다. $N_i$의 합은 500000 이하이다.

자율 주행 자동차가 시범 주행 트랙을 완주하는 데 필요한 최소 이동 횟수를 출력한다. 완주할 수 없다면 -1을 출력한다.