You have been given a graph $G$ consisting of $n$ nodes and $m$ edges. Also, you have been given a multi-set $S$ of size $m$ consisting of integers.

Now, you need to assign a single integer from $S$ as weight to each edge of the graph, such that the weight of the shortest path among node 1 and maximum number of other nodes is a prime number. Let the number of nodes having weight of shortest path among node 1 and itself a prime number be $k$. You need to try and maximize $k$. 

Each element of set $S$ has to be used exactly once, a single integer from the Set being assigned to a single edge of the given graph. 

Input Format :

The first line contains two integers $n$ and $m$.

Each of the next $m$ lnes contains two space separated integers $(u,v)$ indicating an edge between nodes $u$ and $v$ in graph $G$.

The next line contains $m$ space separated integers , where the $i^{th}$ integer indicates the $i^{th}$ element of the given set.

It is guaranteed there will be no self loops and multiple edges, and the given input graph will be connected. 

Output Format :

Print $m$ lines, on the $i^{th}$ line print a single integer $w_i$ denoting the weight assigned to the $i^{th}$edge given in the input in the same order.

Note that the union of all $w_i$ should be equal to the set $S$.

Test Generation Process:

First, a random tree consisting of $n$ nodes is generated using the following pseudo-code :

for (i = 2 to n)
{
   parent[i] = rnd(1, i - 1)

   addEdge(i, parent[i])
}

Next,

while (num_edges < m)
{
    x = rnd(1, n), y = rnd(1, n)

    if (x != y and edge(x, y) is new)
    {
       addEdge(x, y);
    }
}

The elements of the set $S$ are generated randomly , each number with equal probability. The function $rnd(x,y)$  generates a random integer equi-probably in the range $[x,y]$

Scoring :

There are 5 input files

For the first test file :

$n=100,m=700, \max\limits_{x \in S} x=20$

For the next two test files , 

$n=1000, m=10\,000, \max\limits_{x \in S} x = 200$

For the next two test files , 

$n=5000, m = 100\,000, \max\limits_{x \in S} x = 1000$

Additionally, 5 more test files will be added and all submissions will be rejudged with the following constraints :

$n=1000, m=999, \max\limits_{x \in S} x = 200$

$n=1000, m=20\,000, \max\limits_{x \in S} x = 200$

$n=5000, m=4999, \max\limits_{x \in S} x = 1000$

$n=5000, m=1 \ 90 \, 000, \max\limits_{x \in S} x = 1000$

$n=5000, m=2 \ 00\,000, \max\limits_{x \in S} x = 1000$

Let the number of nodes having weight of shortest path between it and node 1 be $k$ in any test file. Your score for that test will be :

$\frac{k}{n-1} \cdot 10$. Your overall score will be the sum of scores over all test files.