putovanje (COCI CONTEST_#4)
Time limit: 2 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: shortest path, dijkstra, bfs, graph traversal

# Task Putovanje

Mr. Malnar has finally reached his annual vacation. The country he decided to travel to can be represented as *n* cities and *m* 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 *a* to city *b* is defined as a sequence of roads such that, starting from city *a* and sequentially traversing the roads in that sequence, one ends up in city *b*. 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.

## Input

In the first line, there are natural numbers *n* and *m* - the number of cities and the number of roads connecting them (1 ≤ *n* ≤ 5 · 10<sup>4</sup>, *n* − 1 < *m* ≤ 10<sup>5</sup>).

In the *i*-th of the following *m* lines, there are numbers *u<sub>i</sub>* and *v<sub>i</sub>* - there is a road between cities *u<sub>i</sub>* and *v<sub>i</sub>* (1 ≤ *u<sub>i</sub>, v<sub>i</sub>* ≤ *n*, *u<sub>i</sub>* ≠ *v<sub>i</sub>*). There is at most one road between any two cities.

In the last line, there are *n* integers - the *i*-th number *d<sub>i</sub>* indicates the distance from the *i*-th city to the city where the hotel is located, or −1 if Mr. Malnar did not record that distance (−1 ≤ *d<sub>i</sub>* < *n*).

## Output

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.

#### Scoring

| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 |  \(m + 1 = n \leq 5000, u_{i+1} = v_i\) for every i |
| 2 | 20 | \(d_i = -1\) for every \(i > 1\) |
| 3 | 35 | \(n, m \leq 5000\) |
| 4 | 45 | No additional constraints. |

## Examples

| input | input | input |
|---|---|---|
| 7 6<br>1 2<br>1 3<br>3 4<br>3 5<br>3 6<br>5 7<br>2 -1 -1 -1 -1 -1 3 | 6 6<br>1 2<br>2 3<br>3 4<br>4 5<br>5 6<br>6 1<br>2 -1 -1 1 -1 -1 | 4 3<br>1 2<br>2 3<br>3 4<br>1 -1 -1 1 |
| output | output | output |
| 2<br>4 6 | 2<br>3 5 | 0 |

#### Clarification of the first example:

The path from the city labeled 4 to the city labeled 1 is of length 2, while the path from the city labeled 4 to the city labeled 7 is of length 3. Therefore, city 4 satisfies both conditions and the hotel can be located there.

The same holds true for the city labeled 6.

Starter code:

Grader code:

Setup script:

Evaluation script: