이 문제는 그래프 문제이다.

N개의 정점과 M개의 간선으로 이루어진 연결 그래프에서, 1번 정점에서 N번 정점으로 가는 최단경로를 찾고자 한다. 모든 간선의 길이는 1이다.

이렇게 문제를 내면 마지막 문제가 될 수 없기 때문에, 정수 L과 길이 L의 배열 V가 주어졌을 때, i+1번째로 방문하는 정점은 V[i%L]이 될 수 없고, i번째에서 i+1번째로 이동할 때 V[i%L]에서 V[(i-1)%L]로 갈 수 없다는 조건이 K개 주어진다. 단, 각 정점은 최대 하나의 배열 V에 포함되고, 1번 정점과 N번 정점은 V에 포함되지 않는다.

이러면 풀 수 없는 경우가 너무 많아지기 때문에, N개의 간선을 더 추가하여 모든 i에 대해 i번 정점에서 i번 정점으로 가는 self loop를 추가한다.

이 그래프에서 최단 경로의 길이를 구하여라. 만약 조건을 만족하는 경로가 없다면 "impossible"을 출력하라.

제한: N<=250000, M<=3000000, 3<=L<=1500, L의 합<=2750

#8191 upload 18 done 1 how_to_reg 1 call_split Subtarea

그래프 문제 1 timer 5s memory 512MB

#8191
Subtarea

그래프 문제 1 5s 512MB