Putovanje

문제

Mr. Malnar has finally reached his annual vacation. The country he decided to travel to can be represented as $nn$ cities and $mm$ bidirectional roads connecting them. Each road has the same length, and it is possible to reach any city from any other by traveling on these roads. A path from city $aa$ to city $bb$ is defined as a sequence of roads such that, starting from city $aa$ and sequentially traversing the roads in that sequence, one ends up in city $bb$. The length of a path is defined as the number of roads on that path.

Mr. Malnar routinely booked the most expensive hotel in one of the cities and then started to plan his journey. To facilitate his planning, he recorded the length of the shortest path needed from the hotel to each city.

Excited about his long-awaited vacation, Mr. Malnar completely forgot in which city the hotel is located. He certainly does not want to miss the trip, so he asks you to determine in which cities the hotel can be located.

입력

In the first line, there are natural numbers $nn$ and $mm$ - the number of cities and the number of roads connecting them (1 ≤ n ≤ 5 \cdot 10^4, n - 1 ≤ m ≤ 10^5).

In the $ii$-th of the following $mm$ lines, there are numbers $u_{i}u\_i$ and $v_{i}v\_i$ - there is a road between cities $u_{i}u\_i$ and $v_{i}v\_i$ (1 ≤ u_i , v_i ≤ n, $u_i\mathrm{\ne }{v}_{i}u\_i\; \backslash ne\; v\_i$). There is at most one road between any two cities.

In the last line, there are $nn$ integers - the $ii$-th number $d_{i}d\_i$ indicates the distance from the $ii$-th city to the city where the hotel is located, or $-1-1$ if Mr. Malnar did not record that distance (-1 &le; d_i < n).

출력

In the first line, write the number of cities where the hotel can be located.

In the second line, write the labels of the cities where the hotel can be located, in ascending order.

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

2
4 6

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

2
3 5

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

0