Problem H
Hill Climbing
SoCCat the Hill Climber is a very determined cat. Currently, SoCCat is climbing the hill of an NPhard problem!
Everyone knows that the graph edge partitioning problem is NPhard. As there are many variants of it, here’s the one that SoCCat is talking about:
There is a connected graph with $n$ vertices and $m$ edges. You can color each edge into $m$ possible colors, numbered from $1$ to $m$. However, you can only color at most $a_ c$ edges with color $c$.
A coloring of a subset of edges is valid if it satisfies all of the following conditions for each color $1 \leq c \leq m$:

There are at most $a_ c$ edges with color $c$.

Every pair of edges with color $c$ is reachable from each other by only using edges with color $c$. In other words, if $V_ c$ is the set of all vertices adjacent to an edge with color $c$, and $E_ c$ is the set of all edges with color $c$, then the subgraph $(V_ c, E_ c)$ is connected.
Note that you can leave some edges uncolored. Uncolored edges do not have to satisfy any of the above conditions.
SoCCat is confident that their hillclimbing algorithm can correctly determine whether a valid coloring with at least $\lceil \frac{n}{2} \rceil $ colored edges exist with $99.8244353\% $ probability.
SoCCat does not believe you could match their algorithm’s performance in a mere $4$ hours. After all, SoCCat took weeks to design and code a very efficient and robust hillclimbing algorithm to do this task.
Can you do it?
Input
The input starts with a line containing an integer $C$, denoting the number of test cases ($1 \leq C \leq 300\, 000$). Each test case has the following format.
The first line contains two integers $n$ and $m$, denoting the number of vertices and the number of edges in the graph, respectively ($2 \leq n \leq 300\, 000$; $n  1 \leq m \leq 300\, 000$). The sum of $n$ and $m$ over all test cases does not exceed $300\, 000$.
The second line contains $m$ spaceseparated integers $a_1, a_2, \ldots , a_ m$, where $a_ i$ denotes the maximum number of edges you can color with color $i$ ($0 \leq a_ i \leq m$; $\sum _ i a_ i \leq m$).
The following $m$ lines each contain two integers $u$ and $v$, denoting an edge between vertices $u$ and $v$ ($1 \leq u, v \leq n$). The graph is guaranteed to be connected and has no selfloops or multiple edges.
Output
For each test case, output Yes if there exists a valid coloring with at least $\lceil \frac{n}{2} \rceil $ colored edges, and No otherwise.
Additionally, if the answer is Yes, output a line containing $m$ spaceseparated integers $c_1, c_2, \ldots , c_ m$. $c_ i$ should be equal to the color of the $i$th edge, or $0$ if the $i$th edge is uncolored ($0 \leq c_ i \leq m$).
There should be at least $\lceil \frac{n}{2} \rceil $ colored edges, and the coloring should be valid. If there are multiple possible answers, output any one of them.
Sample Input 1  Sample Output 1 

4 5 4 4 0 0 0 2 3 2 1 4 5 4 3 6 11 0 0 0 0 0 0 0 3 2 3 3 1 2 2 3 3 4 4 5 5 6 6 1 1 4 4 2 2 5 5 3 4 6 6 11 0 0 0 0 0 0 0 3 2 3 3 1 2 2 3 3 4 4 5 5 6 6 1 1 4 4 2 2 5 5 3 4 6 5 10 1 0 0 0 0 0 0 0 0 1 1 2 2 3 3 4 4 5 5 1 1 3 3 5 5 2 2 4 4 1 
Yes 1 1 0 1 Yes 8 11 10 10 9 8 8 11 9 10 11 Yes 11 11 11 0 0 0 0 0 0 0 0 No 