You are given a cactus with $N$ vertices and $M$ edges. Recall that a cactus is a connected graph where every edge belongs to at most one cycle. Edge $i$ connects vertices $u_i$ and $v_i$. Your friend decided to colour the cactus with $N$ different colours, numbered from $1$ to $N$, with vertex $i$ having colour $c_i$. It may be the case that some colours are not present in the cactus. You are asked to determine for each colour, what is the length of the shortest path between any two distinct vertices of that colour? A path is a list of distinct vertices such that there is an edge between each pair of consecutive vertices in the list. The length of this path is the number of such edges.

Formally, let a path be a list of $L$ vertices $(P_1,P_2,\dots ,P_L)$ such that there is an edge between vertices $P_j$ and $P_{j+1}$ for all $j$ $(1\le j\le L-1)$, and there does not exist a pair $a,b$ where $a\ne b$ and $P_a=P_b$.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask	Points	$N,M,K$	Additional Constraints
$1$	$5\mathrm{\%}$	$1\le N\le 1000$ $N-1\le M\le 1500$	None
$2$	$20\mathrm{\%}$	$1\le N\le 100000$ $N-1\le M\le 150000$	For each colour, there are at most 2 vertices of that colour
$3$	$20\mathrm{\%}$	$1\le N\le 100000$ $M=N-1$	None
$4$	$55\mathrm{\%}$	$1\le N\le 100000$ $N-1\le M\le 150000$	None

For all subtasks:

$1\le u_i,v_i\le N$

$1\le c_i\le N$

The graph is a cactus.

There will be no self loops (an edge from a vertex to itself) and no multiple edges between any two vertices.

Input Specification

The first line contains 2 integers, $N$, and $M$.

The next line contains $N$ integers, describing the colouring of the cactus. The $i^{th}$ integer contains the value $c_i$, the colour of vertex $i$.

The next $M$ lines describe the edges of the cactus. Each line contains 2 integers, $u_i$ and $v_i$, indicating an unweighted bidirectional edge between $u_i$ and $v_i$.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single line containing $N$ space separated integers. The $i^{th}$ integer is the length of the shortest path between two distinct vertices of colour $i$. If there are less than two vertices of that colour, print -1 instead.

Sample Input 1

6 6
1 3 6 6 6 1
1 2
2 3
3 1
1 4
2 5
3 6

Sample Output 1

2 -1 -1 -1 -1 2

Sample Explanation 1

The shortest path between any two vertices of colour $1$ (red) is $1-3-6$.

The shortest path between any two vertices of colour $6$ (green) is $3-2-5$.

All other colours have less than two vertices.

Sample Input 2

5 4
2 5 4 5 4
4 2
5 2
4 1
3 4

Sample Output 2

-1 -1 -1 3 1

Sample Explanation 2

The shortest path between any two vertices of colour $4$ (green) is $3-4-2-5$.

The shortest path between any two vertices of colour $5$ (blue) is $2-4$.

All other colours have less than two vertices.