시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB97262033.333%

문제

코더스하이 주식회사는 최근 유능한 프로그래머들을 고용하여 침입 탐지 시스템을 개발하고 있었다. 알고리즘과 보안 기술에 대한 이해가 높은 인재들이 많은 덕분인지 괄목할만한 성과가 나오고 있었다.

그러던 어느 날 코더스하이 기술자들은 코더스하이 주식회사에 대한 침입 시도를 감지하였다. 다행히도 코더스하이 주식회사의 기술자들은 공격을 시도한 장소로 추정되는 곳들을 알아낼 수 있었다. 그런데 공격을 시도한 범인 일당은 공항으로 도망가려고 하고 있었다!

범인들은 현재 공격을 시도한 위치로 추정되는 장소들 중 한 곳에 머물러 있으며, 유한한 시간 내에 공항들 중 하나에 간다고 가정하자. 물론 범인들이 최단 경로로 이동하리라는 보장은 없다.

다음과 같은 성질을 만족하는 장소 A를 “검문소 후보”라고 하자.

  • 범인이 공격을 시도한 위치로 추정되는 장소들에서는 장소 A를 지나지 않고서는 절대로 공항에 도달할 수 없다.

즉, “검문소 후보”라는 장소에 가서 기다리면 언젠가는 범인들이 지나가게 될 것이다.

당신은 코더스하이 주식회사를 침입하려고 한 범인들을 검거하려고 한다. 이미 모든 장소와 그들을 잇는 모든 도로들의 정보를 빠짐없이 알고 있다. 그리고 공격을 시도한 위치로 추정되는 장소들의 목록과 공항이 있는 장소들의 목록을 코더스하이 기술자들로부터 넘겨 받았다. 당신은 “검문소 후보”의 개수와 그 장소들의 목록을 계산해야 한다.

입력

첫 번째 줄에 장소의 개수 N (2 ≤ N ≤ 100 000)과 도로의 개수 M (1 ≤ M ≤ 200 000)이 공백을 사이로 두고 차례로 주어진다. 각 장소에 1부터 N까지의 번호가 붙어있다고 가정하자.

다음 M개의 줄에 도로의 정보가 주어진다. 이 중 i (1 ≤ iM)번째 줄에는 도로가 잇는 두 장소의 번호를 나타내는 두 정수 aibi (1 ≤ ai, biN, aibi)가 공백을 사이로 두고 차례로 주어진다.

그 다음 줄에는 공격을 시도한 위치로 추정되는 장소들의 개수 S(1 ≤ SN −1)와 공항이 있는 장소들의 개수 E(1 ≤ EN − 1)가 공백을 사이에 두고 차례로 주어진다.

다음 줄에는 공격을 시도한 위치로 추정되는 장소들의 번호 s1, s2, · · · , sS가 공백을 사이에 두고 차례로 주어진다. 마지막 줄에는 공항이 있는 장소들의 번호 e1, e2, · · · , eE가 공백을 사이로 두고 차례로 주어진다. 모든 siei는 중복된 것이 없이 서로 다르다.

단, 모든 장소들은 직간접적으로 항상 연결되어 있다는 것이 보장된다. 즉, 어느 장소에 있든지 임의의 다른 장소로 갈 수 있는 경로가 항상 존재한다는 것이 보장된다. 또한 (ai, bi) = (aj, bj)이고 ij를 만족하는 i, j는 존재하지 않는다. 즉, 어떤 두 장소를 잇는 도로는 많아야 한 개이다.

출력

첫 번째 줄에 “검문소 후보”의 개수를 출력한다.

두 번째 줄에 “검문소 후보”들을 작은 번호부터 차례대로 공백 한 칸을 사이에 두고 출력한다. 검문소 후보가 없는 경우에도 빈 줄을 출력해야 한다.

주의: 공격을 시도한 위치 si와 공항 ei도 “검문소 후보”가 될 수 있다.

예제 입력 1

2 1
1 2
1 1
1
2

예제 출력 1

2
1 2

예제 입력 2

6 6
1 3
2 3
3 4
4 6
4 5
2 4
2 2
1 2
5 6

예제 출력 2

1
4

예제 입력 3

4 4
1 2
2 3
3 4
4 1
2 2
1 2
3 4

예제 출력 3

0

출처

Contest > Coder's High > Coder's high 2016 Round 2: Nexon Arena H번