Shortest Jewel Collection Path

You are given a directed graph with n nodes numbered 1 through n and m directed edges. Each node contains a "light jewel" of a certain type. There are k types of jewels numbered from 0 to k-1. A traveler can start at any node and walk along the directed edges without visiting any node more than once. As soon as he visits a node, he collects the jewel on that node. Once he has collected jewels from k nodes, he stops collecting jewels.

Your task is to find a simple path (i.e. a path with no repeated nodes) of exactly L nodes such that the jewels collected from the first k nodes of the path include all k types (each type must appear at least once). Since he stops collecting after k nodes, extra nodes beyond the first k do not contribute to the jewel collection; therefore, you are required to find the shortest such path which will always have a length of k if it exists. In other words, you need to find a simple path of exactly k nodes such that the set of jewel types on these k nodes is exactly \(\{0,1,\dots,k-1\}\).

If such a path exists, output the number of nodes in the path (which is k); otherwise, output -1.

Note: The jewel on a node is collected only when it is visited and every node has a fixed jewel type. You cannot visit the same node twice.

inputFormat

The first line contains three integers n, m and k: the number of nodes, the number of edges, and the number of jewel types respectively.

The second line contains n integers, where the \(i\)th integer (0-indexed type) represents the jewel type present at node \(i\) (nodes are numbered from 1 to n). Each jewel type is in the range \(0 \leq c < k\).

Each of the next m lines contains two integers u and v indicating a directed edge from node u to node v.

outputFormat

Output a single integer: the length of the shortest valid path (which equals k if such a path exists) or -1 if no valid path exists.

sample

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

3