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.