문제
아래와 같은 무방향의 무가중치 그래프와 이에 대한 경로가 주어진다. 다음은 예를 들기 위해 주어진 그래프이다.
그리고 주어진 경로가 [ 1 2 2 7 5 5 5 7 4 ] 라고 하자.
경로는 1번 노드에서 2번 노드로, 그리고 2번 노드에 머무르다가 7번 노드로 이동하는 순으로 이동을 하려고 한다는 것이다.
하지만 이 경로는 2에서 7로 연결된 경로가 없기 때문에 완전하지 않은 경로이다.
경로가 주어졌을 때, 경로의 잘못된 경로를 최소한의 갯수로 고쳐서 완전한 경로를 만드는 프로그램을 작성하라.
위의 예제의 경우 답은 1이며, 다음과 같이 3가지 방법으로 해결이 가능하다. [1 2 2 4 5 5 5 7 4] [1 2 4 7 5 5 5 7 4] [1 2 2 6 5 5 5 7 4]
입력
입력의 첫 번째 줄에는 정점의 갯수 N(N≤100)과 간선의 갯수 M(M≤4,950)이 입력된다.
그 다음 줄부터 M개의 줄에는 1이상 N이하의 숫자 a와 b가 입력되는데, 이는 정점 a와 정점 b를 연결하는 간선이 존재한다는 것이다.
그 다음에는 경로의 길이 L(L≤200)이 입력되며, 그 다음 한 줄에는 L개의 경로를 이루는 1이상 N이하의 정수가 입력된다.
출력
경로를 완전한 경로로 만들기 위한 변경의 최소 횟수를 출력한다.
예제1
입력
79
12
23
24
26
34
45
56
74
75
9
122755574
출력
1
예제2
입력
79
12
23
24
26
34
45
56
74
75
9122655574
출력
0
출처
UVa 1424 Salesmen