페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7074
서브태스크
다국어

여행 2초 1024MB

문제

말나르 씨는 여행을 떠났다. 그가 여행하려고 결정한 나라는 n 개의 도시와 그들을 연결하는 m 개의 양방향 도로로 나타낼 수 있다. 각 도로의 길이는 동일하며, 이 도로를 통해 어떤 도시에서든 다른 도시로 이동할 수 있다. 도시 a에서 도시 b로의 경로는 a에서 시작하여 그 순서대로 도로를 순차적으로 이동하여 b 도시에 도달하는 도로들로 정의된다. 경로의 길이는 해당 경로 상의 도로 수로 정의된다.

말나르 씨는 규칙적으로 한 도시에서 가장 비싼 호텔을 예약한 다음 여행 계획을 시작했다. 계획을 용이하게하기 위해 호텔에서 각 도시까지 필요한 최단 경로의 길이를 기록했다.

오래 기다렸던 여행에 기대감이 커져 말나르 씨는 호텔이 어느 도시에 있는지 완전히 잊어 버렸다. 말나르씨를 위해 호텔이 위치할 수 있는 도시를 추측하는 프로그램을 작성하시오.


입력

첫 번째 줄에 도시 수를 의미하는 자연수 n과 그 도시들을 연결하는 도로 수 자연수 m이 주어진다. (1 ≤ n ≤ 5 \cdot 10^4, n - 1 ≤ m ≤ 10^5).

다음 m 줄 중 i 번째 줄에 u_i와 v_i가 주어진다. 이는 도시 u_i와 v_i 사이에 도로가 있음을 나타낸다. (1 ≤ u_i , v_i ≤ n, u_i \ne v_i). 두 도시 사이에 최대 한 개의 도로가 있다.

마지막 줄에 n개의 정수가 주어진다. i 번째 숫자 d_i는 i 번째 도시에서 호텔이 있는 도시까지의 거리를 나타내며, 말나르 씨가 해당 거리를 기록하지 않았다면 -1이다 (-1 ≤ d_i < n).


출력

첫 번째 줄에 호텔이 위치할 수 있는 도시 수를 출력한다.

두 번째 줄에 호텔이 위치할 수 있는 도시의 번호들을 오름차순으로 출력한다.


부분문제

번호 점수 조건
#19점

m + 1 = n ≤ 5000,  모든 i에 대해 u_i + 1 = v_i

#218점

모든 i>1에 대해 d_i = -1

#332점

 n, m ≤ 5000

#441점

추가 제한 없음


예제1

입력
76
12
13
34
35
36
57
2-1-1-1-1-13
출력
2
46

도시 4에서 도시 1로 향하는 경로의 길이는 2이고, 도시 4에서 도시 7로 향하는 경로의 길이는 3이다. 그러므로 도시 4는 두 조건을 모두 만족하고 호텔을 거기에 위치시킬 수 있다.

도시 6도 동일한 조건을 만족시킨다.


예제2

입력
66
12
23
34
45
56
61
2-1-11-1-1
출력
2
35

예제3

입력
43
12
23
34
1-1-11
출력
0

출처

COCI 2023/2024 Contest #4 4번

역링크