페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7055

경로 찾기 3초 1024MB

문제

그래프에서 어느 두 정점 사이의 경로는, 두 정점 사이를 간선을 통해 지나가는 방법을 의미한다.

'아름다운 경로'란, 이 경로 상의 모든 정점의 색깔이 전부 다른 경로를 의미한다.

그래프의 구조와, 각 정점의 색깔이 주어질 때 아름다운 경로의 개수를 구하시오.

단, 모든 경로는 정점이 최소 2개 이상 포함되어야 한다.

또한, 같은 정점 집합을 지나가더라도 그 순서가 다르다면 다른 경로로 취급한다. 예를 들어, 1-2와 2-1은 다른 경로이다.


입력

첫 줄에 정점의 개수 N, 간선의 개수 M, 색깔의 개수 K가 주어진다.

그 다음 줄에 각 정점의 색깔을 나타내는 길이 N의 배열이 주어진다. 각 색깔은 1부터 K 사이의 자연수로 표현된다.

그 다음 M개의 줄에 걸쳐 간선의 정보가 u, v의 형태로 주어진다.

N, M, K의 제한은 서브태스크를 참고하여라.


출력

아름다운 경로의 개수를 한 줄에 출력하여라. 단, 이 값은 10^{18}보다 작음이 보장된다.


부분문제

번호 점수 조건
#123점

1\leq N, M\leq 100, 1\leq K\leq 4

#220점

1\leq N, M\leq 300000, 1\leq K\leq 3

#327점

1\leq N, M\leq 300000, 1\leq K\leq 4

#430점

1\leq N, M\leq 100000, 1\leq K\leq 5


예제1

입력
433
1213
12
23
42
출력
10

예제2

입력
9114
123412122
12
13
23
24
36
62
65
43
45
78
98
출력
70

출처

BOI 2018

역링크