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

#7055

경로 찾기 3s 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

4 3 3
1 2 1 3
1 2
2 3
4 2
10

예제 #2

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8
70


출처

BOI 2018
로그인해야 코드를 작성할 수 있어요.