Reconstruct Purchase Records

In this problem, a group of children pooled their money in pairs to purchase two cards at a store. After buying the cards, they raced to a fountain in the city centre; the winner of each race got both cards. In the event of a tie (i.e. if both children reached at exactly the same time), each child took one card.

Later, when all the children gathered, they tried to recall the purchases, but their memories were fuzzy. They remembered only some of the purchase records (i.e. which pair of children jointly purchased the cards) but did not recall who actually won the race. However, each child did remember exactly how many cards they ended up with.

Your task is to reconstruct one possible outcome of each purchase record that is consistent with the final card counts.

Note that if all purchase records were assumed to have been ties, then every child would have received exactly one card from each record they participated in. In other words, if a child participated in t_i records, they would receive t_i cards. If a record instead produced a winner and a loser, the winner would get 2 cards and the loser 0, which is equivalent to adding an extra card for the winner and subtracting one card from the loser compared to the tie scenario.

Mathematically, define for each child i with participation count t_i and final card count x_i the difference d_i = x_i - t_i. Each non-tie record (where an outcome is chosen) between child u and v provides a change of +1 to one child and −1 to the other. Hence, if you decide to change the outcome of a record from tie to a win/loss pair, you effectively add +1 to one child and −1 to the other.

Your solution must decide, for each recorded pair, whether the outcome was a tie (denoted by 0) or a win/loss decision. In the case of a win/loss, output 1 if the first child wins and 2 if the second child wins. The chosen outcomes must satisfy that for every child i: $$\sum_{\text{records including }i} \delta_i = d_i,$$ with \(\delta_i\) being +1 if the child wins in that record, −1 if the child loses, and 0 if the record was a tie. Also note that the sum of all \(d_i\)'s must be 0 (which is a necessary condition, since every record gives out exactly 2 cards).

If there are multiple valid answers, output any one of them.

inputFormat

The input begins with two integers n and m (1 ≤ n, m ≤ 10⁵), where n is the number of children and m is the number of recorded purchase pairs.

The following m lines each contain two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating that child u and child v were in a pair that bought two cards.

The last line contains n integers x₁, x₂, ..., x_n (0 ≤ x_i ≤ 2*t_i, where t_i is the number of records in which child i occurs). It is guaranteed that \(\sum_{i=1}^{n} x_i = 2m\>.

outputFormat

Output a single line containing m integers separated by spaces. The i-th integer represents the outcome for the i-th purchase record in the input order: output 0 if the record is a tie, 1 if in that record the first child wins, and 2 if the second child wins.

sample

3 3
1 2
2 3
1 3
3 1 2

1 0 0