선인장 가게
시간 제한5초메모리 제한1024 MB
각 정점에 값이 붙은 선인장 그래프가 주어질 때, 질의로 주어진 수로 나누어지지 않는 정점을 모두 지운 뒤 남는 연결 성분의 개수를 각 질의마다 구한다.
문제
은퇴한 UT 컴퓨터과학과 교수들은 텍사스 북부의 농장으로 가서 마음껏 정원을 가꾸고 연구를 한다. 이 두 관심사가 겹치는 경우가 흔한데, 놀라운 Upstate Texas Cactus Shoppe(UTCS)가 그렇다.
은퇴한 컴퓨터과학과 교수가 아닌 우리를 위해 설명하자면, 선인장(cactus)은 모든 간선이 많아야 하나의 단순 사이클에 속하는 무방향 그래프이다. 다음은 선인장 사진들이다:
그림 1: 선인장들! 왼쪽 사진은 Calvin Teo, 오른쪽 사진은 Genleorus가 찍었다.
다음은 선인장 그래프의 그림이다:
그림 2: 선인장 그래프! 그림은 David Eppstein이 만들었다.
UTCS에는 선인장이 하나 있다. 선인장의 각 정점에는 꽃 식별자 가 있는데, 이는 선인장의 그 부분에 있는 꽃을 나타낸다. 와 가 약수를 공유하면 그 정점들의 꽃은 서로 비슷하다.
UTCS에서 구매를 하려면 교수가 꽃 식별자 를 가지고 온다. 그러면 그들은 원본 선인장의 복사본을 만들고 가 를 나누지 않는 모든 정점을 제거한다. 또한 삭제된 정점에 하나라도 연결되어 있던 모든 간선도 제거한다. 그 후 선인장은 여러 연결 요소로 나뉠 수 있다. 각 교수는 이 과정을 거친 후 남는 연결 요소의 개수를 궁금해한다. 빈 그래프의 연결 요소는 개이다. 남은 간선만 사용하는 단순 경로가 두 정점 사이에 존재하면 두 정점은 같은 연결 요소에 속한다.
이 모든 자르기와 다듬기는 힘든 일이며, 특히 은퇴한 사람에게는 더욱 그렇다. 교수들의 질문에 답하는 것을 도와줄 수 있는가?
입력
첫째 줄에 공백으로 구분된 세 정수 (), (), ()가 주어진다. 이는 각각 선인장의 정점 수, 선인장의 간선 수, 질문의 수이다. 다음 줄에 공백으로 구분된 개의 정수 ()가 주어진다. 이는 각 정점의 꽃 식별자이다. 다음 개의 줄에 각각 두 정수 와 ()가 주어지며, 와 를 잇는 간선이 있음을 뜻한다. 이 간선들은 연결된 올바른 선인장을 이룬다고 보장된다. 같은 간선이 두 번 나타나지 않으며, 자기 자신을 잇는 간선은 없다.
다음 개의 줄에 각각 교수의 질문 ()가 주어진다.
출력
각 교수의 질문마다, 로 나누어지지 않는 모든 정점을 제거했을 때 남는 연결 요소의 개수를 출력한다.