Treasure Map
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka found a Lviv treasure map.
Lviv can be represented as an undirected connected graph, where vertices represent intersections and edges — roads between them.
According to legend, the treasure is hidden at one of the intersections. The map creators initially found and marked the shortest distance (number of roads) from each intersection to the treasure. After that, for each distance value, the marking from exactly one intersection with that distance was erased. That is, for each value \(d\), if there are \(k\) intersections at distance \(d\), exactly \(k-1\) of them will have the value \(d\) written, and for the remaining one the value is erased.
Your task is to find all intersections where the treasure could be, given the map.
Input
The first line contains two integers \(n\) and \(m\) — the number of intersections and roads, respectively.
Each of the next \(m\) lines contains a pair of numbers \(u_i\) and \(v_i\) — the numbers of intersections connected by the corresponding road. It is guaranteed that the given graph is connected, and does not contain self-loops and multiple edges.
The next line contains \(n\) space-separated integers \(h_i\). The number -1 indicates that the distance to the corresponding intersection was not marked, while any other number indicates the distance from the treasure to the corresponding intersection.
It is guaranteed that the map is valid and its construction matches the description in the problem statement.
Output
In the first line, print a single integer \(c\) — the number of vertices where the treasure could be located.
In the next line, print \(c\) space-separated numbers in ascending order — the numbers of intersections that can contain the treasure.
Constraints
\(2 \le n \le 2 \cdot 10^5\),
\(1 \le m \le 2 \cdot 10^5\),
\(-1 \le h_i < n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 2 2 1 1 3 -1 -1 -1 | 2 2 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 10 1 4 2 3 3 5 7 5 3 4 6 3 2 6 7 2 2 5 1 3 1 -1 -1 -1 2 2 -1 | 1 4 |
Notes
In the first example, the distance to all intersections is unknown. It is easy to verify that only intersections 2 and 3 correspond to the map construction described in the problem statement.
In the second example, the graph shown in the figure below is given.
Only the intersection numbered 4 could contain the treasure.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|