Galaxy Interconnection

And then, eight hundred and eight years ago, an event took place that opened a new era in the history of mankind. The Era of the Great Circle.

Ivan Yefremov, Andromeda: A Space-Age Tale

More than 1000 years have passed since the first ACM ICPC. Several civilizations of our Galaxy, including the Earth, are united in the Great Circle, whose members exchange and relay scientific and cultural information. Because of the way gravity and dark energy flows are spread across the galaxy, bidirectional communication channels run between some pairs of planets. Civilizations use these channels to spread knowledge across the whole Great Circle.

It is time to divide the research between civilizations. Each planet takes one of $k$ main research areas, such as Repagular Calculus or Given String Theory.

The number $k$ is not accidental. The Great Circle grew out of the Initial Circle, a set of $k$ planets whose channels form a single cycle. New channels were investigated and built later, and new planets joined the Great Circle. Communication channels cost a lot of energy, so every planet of the Great Circle has fewer than $k$ channels.

Two planets joined by a direct channel do not take the same research area. They are better off taking different areas and sharing their results.

There is one more rule. Civilizations periodically send expeditions to explore new planets and to visit their neighbors in the Great Circle. A ship flies from one planet to another only when a communication channel joins them. One kind of expedition is called a Research Audit: the ship starts at some planet, makes $k - 1$ jumps along channels, and visits $k$ planets in total, counting the origin. Those $k$ planets have to take all $k$ research areas, one each, so that the expedition checks every part of the research. All $k$ areas show up along the route, so the visited planets are different from one another.

The Council of the Great Circle has published one assignment: planet $i$ takes area $a_i$. Review it. If a channel joins two planets that took the same area, the assignment already breaks the first rule. Otherwise, count the planets that a Research Audit can start from.

The first line contains the number of planets $n$, the number of research areas $k$, and the number of communication channels $m$ ($3 \le n \le 5000$, $3 \le k \le \min(n, 10)$, $1 \le m \le 10000$).

Each of the next $m$ lines describes one channel by the numbers of the two planets it joins. Planets are numbered from $1$ to $n$, and planets $1$ through $k$ form the Initial Cycle. Every planet has fewer than $k$ channels, and any two planets of the Great Circle are reachable from each other along channels.

The last line contains the assignment as $n$ integers. The $i$-th of them, $a_i$, is the research area taken by planet $i$ ($1 \le a_i \le k$).

If a communication channel joins two planets that took the same research area, print $-1$.

Otherwise print how many planets a Research Audit can start from.