Experimental Treatment

Time limit2sMemory limit1024 MB

Summary

Given n pairs of pill types, pick one type from each pair so that type j is picked exactly c_j times, or report -1 if impossible.

Level: Medium6 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

After many failed attempts to diagnose a new patient, House decided to try an experimental treatment. Throughout the treatment, every hour Foreman offered the patient a choice between two pills. Half an hour after the patient took the $n$ -th pill, his health improved sharply and he miraculously survived. The patient remembers how many pills of each type he took, and Foreman remembers every pair of pills he offered. So that doctors can later treat people with the same symptoms, House wants to restore the type of each pill the patient took. He asked you for help.

Input

The first line contains the number of pills the patient took, $n$ , and the number of different pill types in the hospital, $m$ ( $1 \le n \le 1000$ , $2 \le m \le 1000$ ). Lines 2 through $(n+1)$ each contain a pair of integers $a_i$ , $b_i$ ( $1 \le a_i, b_i \le m$ , $a_i \ne b_i$ ), the types of pills Foreman offered at hour $i-1$ . The last line contains $m$ integers $c_j$ , where $c_j$ is the number of pills of type $j$ that the patient took ( $0 \le c_j \le n$ ). Pill types are numbered starting from 1.

Output

Print a sequence of $n$ numbers, where the $i$ -th number is the type of the pill taken at hour $i$ . If there are several answers, you may print any of them. If no answer exists, print a single number $-1$ .

Examples2

Example 1
Input
```
3 3
1 2
1 3
2 3
1 2 0
```
Expected output
```
2 1 2
```
Example 2
Input
```
3 3
1 2
1 3
2 3
1 1 0
```
Expected output
```
-1
```