시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB87532326437.447%

문제

저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다.

지수는 이 사실을 토대로 당시 폭탄이 떨어진 지점들을 알아내기 위해 우리를 초대했다. 우리는 폭탄이 떨어진 지점들을 전부 알아내야 한다. 어떤 방법으로도 지도와 같은 모양이 나오지 않을 수 있다. 이 경우도 판별해보자.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 2000)과 도로의 개수 M(1 ≤ M ≤ min(N×(N-1)/2, 100,000))이 주어진다.

그 다음 M개의 줄에는 도시 Ui와 Vi가 주어진다. (1 ≤ Ui, Vi ≤ N)

이는 도시 Ui와 Vi가 하나의 도로로 연결되었음을 의미한다. UiVi가 같은 경우는 없으며, 같은 도시 쌍을 잇는 도로는 최대 하나만 존재한다.

그 다음 줄에 파괴된 도시의 개수 K(1 ≤ KN)가 주어진다.

그 다음 줄에 파괴된 도시의 번호를 의미하는 K개의 정수 Pi(1 ≤ PiN)가 공백으로 구분되어 주어진다. 파괴된 도시의 번호가 중복되는 경우는 없다.

출력

만약, 어떤 경우라도 지도와 같은 모양이 나오지 않는다면 -1을 출력하라.

그렇지 않은 경우, 첫째 줄에 폭탄이 떨어진 도시의 개수 T를 출력하라.

그 다음 줄에는 폭탄이 떨어진 도시의 번호를 의미하는 T개의 정수를 공백으로 구분하여 출력하라. 출력에 중복된 도시의 번호가 존재해선 안된다.

만약, 정답으로 가능한 경우가 여러 가지라면 그중 하나를 출력하라.

예제 입력 1

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
1 2 3 4

예제 출력 1

-1

어떤 도시를 골라도 모든 도시와 인접해있기 때문에 위 지도가 가능한 경우는 없다.

예제 입력 2

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

예제 출력 2

2
1 4

1 4 / 1 5 / 1 4 5 이 세가지 경우가 위 지도로 가능한 모든 경우이다.

예제 입력 3

11 14
1 2
1 3
1 9
1 10
1 4
1 6
9 10
9 8
3 10
10 11
6 8
6 7
6 5
4 5
10
10 3 1 9 11 8 6 7 4 5

예제 출력 3

3
5 6 10

출처

University > 인천대학교 > INU 송년 코드페스티벌 2019 D번