Canadian Informatics Workshop 2026: Day 1, Problem 1

It's Black Friday! Linx is at the mall with her friends, hoping to get some good deals. Linx has a shopping list of ~K~ items, labeled 1 to ~K~ that she wants to buy.

The mall contains ~N~ locations, each labeled with a number ~L_i~ from ~-1~ to ~K~.

• A location labeled ~i~ with ~1 \leq i \leq K~ is a shop that sells item ~i~.

• A location labeled ~0~ denotes an entrance to the mall.

• A location labeled ~-1~ is a shop that does not sell any of the ~K~ items that Linx wants.

The locations are connected by ~M~ bidirectional paths, each taking 1 unit of time to traverse, and it is guaranteed that there is a route between any two locations.

Since Linx is a bit of a perfectionist, she wants to purchase all ~K~ items in ascending order, from item 1 to item ~K~. The mall may have multiple entrances, which are all equally accessible from the bus stop, so Linx can start her shopping spree at any entrance (denoted by ~L_i = 0~). She also doesn't mind visiting a shop more than once.

Input Specification

The first line of input contains three space-separated integers ~N~, ~M~, and ~K~ (~1 \leq N, M \leq 2 \times 10^5, 1 \leq K \leq 5~).

The next line contains ~N~ space-separated integers, ~L_i~ (~-1 \leq L_i \leq K~), indicating the label for each location. It is guaranteed that each number from ~0~ to ~K~ appears at least once.

The next ~M~ lines each contain two space-separated integers, ~A_i~ and ~B_i, (1 \leq A_i, B_i \leq 2 \times 10^5)~, indicating that there is a path between the ~A_i~-th and ~B_i~-th location, which takes 1 unit of time to traverse. The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Bounds on ~K~	Additional Constraints
3 marks	~1 \leq N \leq 2 \times 10^5~	~K \leq 5~	There is only one entrance (i.e. ~L_i = 0~ for exactly one ~i~), ~M = N - 1~, and ~A_i + 1 = B_i~ for all ~i~
5 marks	~1 \leq N \leq 2 \times 10^5~	~K = 1~	There is only one entrance (i.e. ~L_i = 0~ for exactly one ~i~)
2 marks	~1 \leq N \leq 2 \times 10^5~	~K = 1~	None
4 marks	~1 \leq N \leq 2 \times 10^5~	~K \leq 5~	There is only one shop of each type. That is, ~L_i = k~ for exactly one ~i~ for every ~1 \leq k \leq K~
3 marks	~1 \le N \le 10~	~K \leq 5~	None
8 marks	~1 \leq N \le 2 \times 10^5~	~K \leq 5~	None

Output Specification

On a single line, output the least amount of time Linx must take to purchase all ~K~ items on her shopping list. It can be shown that this is always possible.

Sample Input 1

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

Sample Output 1

4

Explanation for Sample Output 1

Linx starts at the entrance at location 1. She then travels to location 2 and purchases item 1 there. Next, she travels to location 3 but does not purchase anything. Then, she travels to location 4 and purchases item 2 there. Finally, Linx returns to location 3 to purchase item 3. The total time taken is 4 units, following the location path ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3~.

Sample Input 2

7 8 3
3 -1 0 1 0 2 1
3 4
3 7
3 1
5 7
6 7
7 2
7 1
1 2

Sample Output 2

4

Explanation for Sample Output 2

An example of the shortest path that Linx can take is ~3 \rightarrow 7 \rightarrow 6 \rightarrow 7 \rightarrow 1~.
That is, Linx starts at the entrance at location 3. She then travels to location 7 and purchases item 1. Next, she travels to location 6 and purchases item 2. Then, she returns to location 7 but does not purchase anything. Finally, Linx travels to location 1 and purchases item 3.