Wesley's Anger Contest 1 Problem 6 - Colourful Cactus Ordeal

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.5s
Java 4.5s
Memory limit: 256M
Java 512M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 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 exists a pair a, b where a \neq 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\% 1 \le N \le 1\,000
N - 1 \le M \le 1\,500
None
2 20\% 1 \le N \le 100\,000
N - 1 \le M \le 150\,000
For each colour, there are at most 2 vertices of that colour
3 20\% 1 \le N \le 100\,000
M = N - 1
None
4 55\% 1 \le N \le 100\,000
N - 1 \le M \le 150\,000
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.


Comments

There are no comments at the moment.