Rigged Roads

Silvermill is on a tight budget lately, and Peanut, its mayor, plans to demolish some roads to save on maintenance costs. Silvermill has $N$ road intersections and $E$ roads running between them. The $i$-th road connects intersections $A_i$ and $B_i$. Intersections are labelled $1, \ldots, N$ and roads are labelled $1, \ldots, E$. Any two intersections can reach each other directly or indirectly, and no two roads share the same endpoints.

Peanut has hired you to assess the maintenance cost of the roads. Your task is to report a list $W = (W_1, \ldots, W_E)$ where $W$ is a permutation of $1, \ldots, E$ and $W_i$ is the cost to keep road $i$.

Peanut then keeps a subset of roads such that all intersections remain connected and the total cost of the kept roads is minimal. In other words, Peanut keeps the minimum spanning tree under the weights you choose. The costs are distinct, so the minimum spanning tree is unique.

You have a hidden agenda. You want Peanut to keep a set $R$ of roads that forms a spanning tree, and you can make that happen by choosing $W$ carefully. Find the lexicographically smallest permutation $W$ for which the minimum spanning tree of the city is $R$.

$(W_1, \ldots, W_E)$ is smaller than $(W'_1, \ldots, W'_E)$ if there is a $p$ with $1 \le p \le E$ such that $W_p < W'_p$ and $W_i = W'_i$ for all $i < p$.

Read from standard input. The first line contains two integers $N$ and $E$. The next $E$ lines contain the two integers $A_i$ and $B_i$ describing road $i$. The last line contains $N - 1$ integers, the labels of the roads in $R$.

Print to standard output. Print $E$ integers on a single line, the lexicographically smallest permutation $W$ that makes $R$ the minimum spanning tree.

$1 \le N, E \le 3 \times 10^5$

$1 \le A_i \ne B_i \le N$

$1 \le R_i \le N$

It is possible to travel between any two road intersections using only roads in $R$.