Page not loading? Try clicking here.
Placeholder

#2276

[중등부] 2024 KOI 2차대회 대비 모의고사 (1주차)

Travel
Subtask
2s 1024MB

Problems

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 \cdot 10^4, n - 1 ≤ m ≤ 10^5).

In the i-th of the following m lines, there are numbers u_i and v_i - there is a road between cities u_i and v_i (1 ≤ u_i , v_i ≤ n, u_i \ne v_i). There is at most one road between any two cities.

In the last line, there are n integers - the i-th number d_i 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_i < 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.


Subtask

# Score Condition
#19

 m + 1 = n ≤ 5000, u_i + 1 = v_i for every i

#218

 d_i = -1 for every i > 1

#332

 n, m ≤ 5000

#441

No additional constraints.


Example #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

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.


Example #2

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

Example #3

4 3
1 2
2 3
3 4
1 -1 -1 1
0
You must sign in to write code.