Hide

Problem G
Пути

Submissions to this problem will only be marked as accepted if they receive at least a score of 100
Languages de en et is ja lt lv no pl ru sv

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

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

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

Ввод

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

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

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

Вывод

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

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Группа

Очки

Ограничения

1

23

1N,M100,1K4

2

20

1N,M300000,1K3

3

27

1N,M300000,1K4

4

30

1N,M100000,1K5

Объяснение примера 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.

Пример ввода 1 Пример вывода 1
4 3 3
1 2 1 3
1 2
2 3
4 2
10
Пример ввода 2 Пример вывода 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
Hide

Please log in to submit a solution to this problem

Log in