겁 많은 조깅 동호회
시간 제한1초메모리 제한256 MB
1번 교차로에서 출발해 정해진 거리를 뛰고 돌아올 때 지날 수 있는 모든 구간에 가로등이 닿도록 추가 가로등을 가장 적게 배치합니다.
문제
숲에 조깅용 산책로가 놓여 있다. 교차점은 개이고 산책로는 개이며, 어느 두 교차점 사이에도 산책로를 따라가는 경로가 정확히 하나 있다. 즉 산책로 전체가 하나의 트리를 이룬다.
조깅하는 사람은 모두 1번 교차점에서 출발해 정확히 미터를 달린 뒤 다시 1번 교차점으로 돌아온다. 달리는 도중 교차점이 아닌 산책로 한가운데에서도 방향을 바꿀 수 있고, 원하는 만큼 여러 번 바꿔도 된다. 누가 어느 경로로 달릴지는 알 수 없으므로, 이 조건을 만족하는 경로는 모두 실제로 쓰일 수 있다고 본다. 산책로의 일부만 밟고 되돌아온 경우에도 그 산책로를 이용한 것으로 친다.
밤에는 숲이 어둡다. 사람들은 자기가 지날 수 있는 산책로가 전부 밝기를 원한다. 산책로는 양 끝 교차점 중 적어도 한 곳에 가로등이 있으면 밝다. 이미 가로등이 설치된 교차점이 개 있고, 그 가로등은 그대로 쓴다.
쓰일 수 있는 산책로가 모두 밝아지도록 교차점에 가로등을 추가로 설치하려고 한다. 추가로 설치해야 하는 가로등의 최소 개수를 구하시오.
입력
첫 줄에 교차점의 개수 과 달리는 거리 가 주어진다. (, )
다음 개의 줄에는 각각 세 정수 , , 가 주어진다. 교차점 와 를 잇는 길이 미터의 양방향 산책로가 있다는 뜻이다. (, )
다음 줄에 이미 가로등이 설치된 교차점의 개수 이 주어진다. ()
그 다음 줄에 가로등이 설치된 교차점 번호 개가 공백으로 구분되어 주어진다. 번호는 모두 서로 다르다. 이 이면 이 줄은 비어 있다.
출력
추가로 설치해야 하는 가로등의 최소 개수를 한 줄에 출력한다.