여행

시간 제한2초메모리 제한1024 MB

요약

연결된 그래프에서 일부 도시까지의 최단 거리(-1은 미기록)가 주어질 때, 호텔이 있을 수 있는 모든 도시를 찾습니다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 비트 연산
정답자: 아직 제출이 없습니다

문제

맬나르 씨는 드디어 매년 가는 휴가를 맞았다. 그가 여행하려는 나라는 $n$ 개의 도시와 이를 잇는 $m$ 개의 양방향 도로로 나타낼 수 있다. 도로의 길이는 모두 같고, 이 도로들을 따라 어느 도시에서든 다른 모든 도시로 갈 수 있다. 도시 $a$ 에서 도시 $b$ 까지의 경로는 도시 $a$ 에서 출발해 도로를 순서대로 지나 도시 $b$ 에 도달하는 도로의 나열이다. 경로의 길이는 그 경로에 포함된 도로의 수다.

맬나르 씨는 늘 가장 비싼 호텔을 한 도시에 예약한 뒤 여행을 계획했다. 계획을 돕기 위해 그는 호텔에서 각 도시까지 최단 경로의 길이를 기록했다.

여행을 기대하던 맬나르 씨는 호텔이 어느 도시에 있었는지 잊어버렸다. 그는 여행을 놓치고 싶지 않아 하며, 호텔이 있을 수 있는 도시를 구해 달라고 부탁한다.

입력

첫 줄에 자연수 $n$ 과 $m$ 이 주어진다. 각각 도시의 수와 도로의 수이다 ( $1 \le n \le 5 \cdot 10^4$ , $n - 1 \le m \le 10^5$ ).

이어지는 $m$ 개의 줄에는 $u_i$ 와 $v_i$ 가 주어지며, 도시 $u_i$ 와 도시 $v_i$ 를 잇는 도로가 있다는 뜻이다 ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ ). 두 도시를 잇는 도로는 최대 하나다.

마지막 줄에는 $n$ 개의 정수가 주어진다. $i$ 번째 수 $d_i$ 는 $i$ 번 도시에서 호텔이 있는 도시까지의 거리이며, 기록하지 않았다면 $-1$ 이다 ( $-1 \le d_i < n$ ).

출력

첫 줄에 호텔이 있을 수 있는 도시의 수를 출력한다.

둘째 줄에는 그 도시의 번호를 오름차순으로 출력한다.

예제3

예제 1

입력

7 6
1 2
1 3
3 4
3 5
3 6
5 7
2 -1 -1 -1 -1 -1 3

예상 출력

2
4 6

예제 2

입력

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

예상 출력

2
3 5

예제 3
입력
```
4 3
1 2
2 3
3 4
1 -1 -1 1
```
예상 출력
```
0
```