은하 상호연결

그리고 808년 전, 인류 역사에 새로운 시대를 연 사건이 일어났다. 대원환의 시대다.

이반 예프레모프, 안드로메다 성운

첫 ACM ICPC로부터 1000년이 넘게 흘렀다. 지구를 비롯한 은하의 여러 문명이 대원환에 모여 과학 정보와 문화 정보를 주고받고 중계한다. 은하에 중력과 암흑 에너지 흐름이 퍼진 모양 때문에, 일부 행성 쌍 사이에는 양방향 통신 채널이 놓여 있다. 문명은 이 채널로 지식을 대원환 전체에 퍼뜨린다.

이제 문명끼리 연구를 나눌 때가 됐다. 행성마다 $k$개 주요 연구 분야 가운데 하나를 맡는다. 반복 대수학이나 주어진 끈 이론 같은 분야다.

$k$라는 수는 우연이 아니다. 대원환은 초기 원환에서 시작했다. 초기 원환은 채널이 하나의 사이클을 이루도록 이어진 $k$개 행성이다. 이후 새 채널을 발견하고 건설하면서 새 행성이 대원환에 이어졌다. 통신 채널은 에너지 비용이 커서, 대원환의 모든 행성에 이어진 채널은 $k$개보다 적다.

채널로 직접 이어진 두 행성은 같은 연구 분야를 맡지 않는다. 서로 다른 분야를 맡고 연구 결과를 나누는 편이 낫기 때문이다.

규칙이 하나 더 있다. 문명은 새 행성을 탐사하고 대원환의 이웃을 방문하려고 주기적으로 원정대를 보낸다. 우주선은 통신 채널이 이어 주는 두 행성 사이만 오간다. 그중 연구 감사라고 부르는 원정은 어떤 행성에서 출발해 채널을 따라 $k - 1$번 도약하고, 출발지를 포함해 행성 $k$개를 방문한다. 이 $k$개 행성이 $k$개 연구 분야를 하나씩 모두 맡고 있어야 원정대가 연구 진행 상황을 빠짐없이 점검한다. 분야 $k$개가 모두 나오므로 방문하는 행성도 서로 다르다.

대원환 의회가 배정안 하나를 공개했다. 행성 $i$는 분야 $a_i$를 맡는다. 이 배정안을 검토하라. 채널로 직접 이어진 두 행성이 같은 분야를 맡았다면 첫 번째 규칙부터 어긴 것이다. 그렇지 않다면 연구 감사를 출발시킬 수 있는 행성이 몇 개인지 세어라.

첫 줄에 행성 수 $n$, 연구 분야 수 $k$, 통신 채널 수 $m$이 주어진다. ($3 \le n \le 5000$, $3 \le k \le \min(n, 10)$, $1 \le m \le 10000$)

다음 $m$개 줄에 채널이 한 줄에 하나씩 주어진다. 각 줄에는 그 채널이 잇는 두 행성의 번호가 있다. 행성 번호는 $1$부터 $n$까지이고, 번호가 $1$부터 $k$까지인 행성이 초기 원환을 이룬다. 모든 행성에 이어진 채널은 $k$개보다 적고, 대원환의 두 행성은 언제나 채널을 따라 오갈 수 있다.

마지막 줄에 배정안이 정수 $n$개로 주어진다. $i$번째 정수 $a_i$는 행성 $i$가 맡은 연구 분야 번호다. ($1 \le a_i \le k$)

채널로 직접 이어진 두 행성이 같은 연구 분야를 맡은 경우가 하나라도 있으면 $-1$을 출력한다.

그런 경우가 없으면 연구 감사를 출발시킬 수 있는 행성의 수를 출력한다.