You are given a weighted array that contains $N$ elements and a graph with $N$ vertices and $M$ edges. Determine a valid assignment of weights to vertices such that the value of $E$ is maximum.

Here, $E$ denotes the summation over all edges $max\ (weight[u],\ weight[v])$ and $(u,\ v)$ belongs to $M$.

The assignment of weights must be valid by considering the following points:

1. Every weight must be assigned to exactly one vertex.
2. All weights must be assigned.

Input format

• First line: Two integers denoting $N$, $M$
• Next $M$ lines: Two integers $u$, $v$ denoting an edge between vertex $u$ and vertex $v$

Output format

Print $N$ elements where the $i^{th}$ element is the value of weight assigned to vertex $i$. 

Constraints

$1 \le N \le 1e5\\ 1 \le M \le 1e5\\ 0 \le Weight[] \le 1e6$