Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 07:30 UTC

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 12:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -639 days 22:54:04

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Пути

Граф – это структура, состоящая из множества вершин, и множества ребер. Каждое ребро соединяет две вершины. На иллюстрации ниже показан пример графа с $4$ вершинами и $3$ ребрами.

Путь в графе – это последовательность из $2$ или более вершин, соединённых последовательно рёбрами. Обратите внимание, что порядок вершин играет роль. Например, “5-6-7”, “5-7-6” и “7-6-5” – это разные пути.

В данной задаче каждая вершина графа раскрашена в один из $K$ цветов. Задача состоит в том, чтобы найти количество возможных путей, в которых никакие две вершины не имеют один и тот же цвет.

Input

На первой строке даны три целых числа: $N$ (число вершин), $M$ (число рёбер), и $K$ (число различных цветов).

На второй строке даны $N$ целых чисел между $1$ и $K$ – цвета каждой вершины (начиная с $1$ до $N$).

Каждая из следующих $M$ строк описывает одно ребро, и содержит два целых числа $a, b$ ($1 \le a, b \le N, a \neq b$) – две вершины, соединённых соответствующим ребром. Две вершины не могут быть соединены более чем одним ребром.

Output

Выведите одно целое число – количество различных путей, все вершины которых имеют разные цвета. Известно, что ответ не превышает $10^{18}$.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

1

23

$1 \le N, M \le 100, 1 \le K \le 4$

2

20

$1 \le N, M \le 300\, 000, 1 \le K \le 3$

3

27

$1 \le N, M \le 300\, 000, 1 \le K \le 4$

4

30

$1 \le N, M \le 100\, 000, 1 \le K \le 5$

Explanation of Sample 1

\includegraphics[width=5cm]{pathsfig.pdf}

Граф в первом примере проиллюстрирован на рисунке выше, где каждая вершина раскрашена в белый (цвет 1), серый (цвет 2) или чёрный (цвет 3). Всего есть 10 путей, в которых все вершины имеют различные цвета: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” and “4-2-3”.

Обратите внимание, что “1” не считается подходящим путём, т.к. это всего лишь одна вершина. Не подходит и путь “1-2-3”, т.к. содержит две вершины цвета $1$.

Sample Input 1 Sample Output 1
4 3 3
1 2 1 3
1 2
2 3
4 2
10
Sample Input 2 Sample Output 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