Background

Translated from COCI 2023/2024 Contest #4 Task 4 “Putovanje”.

Problem Description

Mr. Malnar has finally reached his annual vacation. The country he decided to visit can be represented as $n$ cities and $m$ bidirectional roads connecting them. All roads have the same length, and it is possible to travel from any city to any other city using these roads. A path from city $a$ to city $b$ is defined as a sequence of roads such that, starting from city $a$, you traverse the roads in that order and eventually arrive at city $b$. The length of a path is defined as the number of roads on that path.

As usual, Mr. Malnar booked the most expensive hotel in one of the cities and then started planning his trip. To make planning easier, he wrote down the shortest path length from the hotel to every city.

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

Input Format

The first line contains two integers $n$ and $m\ (1\le n\le 5\cdot 10^4,n-1\le m\le 10^5)$, representing the number of cities and roads.

The next $m$ lines each contain two integers $u_i,v_i\ (1\le u_i,v_i\le n,u_i\neq v_i)$, meaning there is a road between cities $u_i$ and $v_i$. There is at most one road between any pair of cities.

The last line contains $n$ integers. The $i$-th integer $d_i\ (-1\le d_i<n)$ denotes the path length from city $i$ to the city where the hotel is located; if Mr. Malnar did not record this value, it is $-1$.

Output Format

On the first line, output how many cities the hotel could be located in.

On the second line, output the indices of the cities where the hotel could be located, in increasing 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

Hint

Sample Explanation 1

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

The same also applies to city $6$.

Subtasks

Translated by ChatGPT 5