You are given a cactus with vertices and edges. Recall that a cactus is a connected graph where every edge belongs to at most one cycle. Edge connects vertices and . Your friend decided to colour the cactus with different colours, numbered from to , with vertex having colour . 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 vertices such that there is an edge between vertices and for all , and there does not exist a pair where and .
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 | Additional Constraints | |
---|---|---|---|
|
None | ||
|
For each colour, there are at most 2 vertices of that colour | ||
|
None | ||
|
None |
For all subtasks:
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, , and .
The next line contains integers, describing the colouring of the cactus. The integer contains the value , the colour of vertex .
The next lines describe the edges of the cactus. Each line contains 2 integers, and , indicating an unweighted bidirectional edge between and .
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 space separated integers. The integer is the length of the shortest path between two distinct vertices of colour . 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 (red) is .
The shortest path between any two vertices of colour (green) is .
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 (green) is .
The shortest path between any two vertices of colour (blue) is .
All other colours have less than two vertices.
Comments