시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 875 | 323 | 264 | 37.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가 하나의 도로로 연결되었음을 의미한다. Ui와 Vi가 같은 경우는 없으며, 같은 도시 쌍을 잇는 도로는 최대 하나만 존재한다.
그 다음 줄에 파괴된 도시의 개수 K(1 ≤ K ≤ N)가 주어진다.
그 다음 줄에 파괴된 도시의 번호를 의미하는 K개의 정수 Pi(1 ≤ Pi ≤ N)가 공백으로 구분되어 주어진다. 파괴된 도시의 번호가 중복되는 경우는 없다.
만약, 어떤 경우라도 지도와 같은 모양이 나오지 않는다면 -1
을 출력하라.
그렇지 않은 경우, 첫째 줄에 폭탄이 떨어진 도시의 개수 T를 출력하라.
그 다음 줄에는 폭탄이 떨어진 도시의 번호를 의미하는 T개의 정수를 공백으로 구분하여 출력하라. 출력에 중복된 도시의 번호가 존재해선 안된다.
만약, 정답으로 가능한 경우가 여러 가지라면 그중 하나를 출력하라.
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
어떤 도시를 골라도 모든 도시와 인접해있기 때문에 위 지도가 가능한 경우는 없다.
5 3 1 2 3 2 5 4 4 1 2 4 5
2 1 4
1 4 / 1 5 / 1 4 5 이 세가지 경우가 위 지도로 가능한 모든 경우이다.
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 5 6 10
University > 인천대학교 > INU 송년 코드페스티벌 2019 D번