무방향 그래프에서 출발 후보 정점 집합과 공항 정점 집합이 주어질 때, 모든 출발 후보에서 공항으로 가는 모든 경로가 반드시 지나는 정점의 개수와 목록을 구한다.
어려움8그래프DFS아직 제출이 없습니다시간 제한2초메모리 제한128 MB코더스하이는 유능한 프로그래머를 모아 침입 탐지 시스템을 개발했다. 알고리즘과 보안 기술에 밝은 인재가 많아 성과도 빨리 나왔다.
그러던 어느 날 코더스하이 기술자들이 회사를 겨냥한 침입 시도를 탐지했다. 다행히 공격이 시도된 것으로 추정되는 장소를 모두 알아냈다. 그런데 범인 일당은 공항으로 달아나려 한다.
범인은 공격이 시도된 것으로 추정되는 장소 중 한 곳에 머물러 있고, 유한한 시간 안에 공항 중 한 곳으로 이동한다고 하자. 범인이 최단 경로로 움직인다는 보장은 없다.
다음 성질을 만족하는 장소 A를 검문소 후보라고 부른다.
즉, 검문소 후보에서 기다리면 범인은 언젠가 그 장소를 지나간다.
당신은 모든 장소와 그 장소를 잇는 도로 정보를 빠짐없이 알고 있고, 공격이 시도된 것으로 추정되는 장소의 목록과 공항이 있는 장소의 목록도 기술자에게서 넘겨받았다. 검문소 후보가 몇 개인지, 그리고 그 장소가 어디인지 구하라.
첫째 줄에 장소의 개수 N (2≤N≤100000)과 도로의 개수 M (1≤M≤200000)이 공백을 사이에 두고 주어진다. 각 장소에는 1번부터 N번까지 번호가 붙어 있다.
다음 M개의 줄에 도로 정보가 주어진다. 그중 i번째 줄에는 도로가 잇는 두 장소의 번호 ai와 bi (1≤ai,bi≤N, ai=bi)가 공백을 사이에 두고 주어진다.
그다음 줄에는 공격이 시도된 것으로 추정되는 장소의 개수 S (1≤S≤N−1)와 공항이 있는 장소의 개수 E (1≤E≤N−1)가 공백을 사이에 두고 주어진다.
다음 줄에는 공격이 시도된 것으로 추정되는 장소의 번호 s1,s2,…,sS가 공백을 사이에 두고 주어진다. 마지막 줄에는 공항이 있는 장소의 번호 e1,e2,…,eE가 공백을 사이에 두고 주어진다. si는 서로 다르고, ei도 서로 다르다.
모든 장소는 직접 또는 간접으로 연결되어 있다. 즉, 어느 장소에서든 다른 임의의 장소로 가는 경로가 항상 있다. 또한 i=j이면서 (ai,bi)=(aj,bj)인 i, j는 없다. 즉, 두 장소를 잇는 도로는 많아야 한 개다.
첫째 줄에 검문소 후보의 개수를 출력한다.
둘째 줄에 검문소 후보를 번호가 작은 것부터 차례대로 공백 한 칸을 사이에 두고 출력한다. 검문소 후보가 없으면 둘째 줄은 빈 줄로 출력한다.
공격이 시도된 것으로 추정되는 장소 si와 공항이 있는 장소 ei도 검문소 후보가 될 수 있다.