Hotel Mystery

Mr. Malnar finally got his annual vacation. He booked the most expensive hotel in one of the cities of a country that can be represented by \(n\) cities and \(m\) bidirectional roads of equal length. The country is connected, i.e. one can travel between any two cities using these roads.

A path from city \(a\) to city \(b\) is defined as a sequence of roads such that starting from \(a\), following the sequence of roads leads to \(b\). The length of a path is the number of roads it contains.

Before his trip, Mr. Malnar recorded the shortest path length from the hotel to every city. However, in his excitement for the long-awaited vacation, he completely forgot which city hosts the hotel. Help him determine all the possible cities where the hotel might be located.

Note that if a city \(h\) is the hotel, then the shortest distance from \(h\) to itself should obviously be \(0\), and the shortest path distances from \(h\) to every other city, computed via a bread-first search (BFS) for an unweighted graph, should exactly match the recorded values.

The road network is given and it is guaranteed that the graph is connected.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of cities and \(m\) is the number of roads.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that there is a bidirectional road between cities \(u\) and \(v\).

The last line contains \(n\) integers \(d_1, d_2, \ldots, d_n\), where \(d_i\) represents the recorded shortest distance from the hotel to city \(i\).

You may assume that \(1 \leq u, v \leq n\) and the graph is connected.

outputFormat

Output in one line all possible hotel cities (their indices in increasing order) that satisfy that when chosen as the start city, the computed shortest distances to all other cities exactly match the recorded distances. If there is no such city, output -1.

sample

4 3
1 2
2 3
3 4
2 1 0 1

3