Problem G
Пути
Граф – это структура, состоящая из множества
вершин, и множества ребер. Каждое ребро
соединяет две вершины. На иллюстрации ниже показан пример графа
с
Путь в графе – это последовательность из
В данной задаче каждая вершина графа раскрашена в один из
Ввод
На первой строке даны три целых числа:
На второй строке даны
Каждая из следующих
Вывод
Выведите одно целое число – количество различных путей, все
вершины которых имеют разные цвета. Известно, что ответ не
превышает
Ограничения
Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.
Группа |
Очки |
Ограничения |
1 |
23 |
|
2 |
20 |
|
3 |
27 |
|
4 |
30 |
|
Объяснение примера 1
Граф в первом примере проиллюстрирован на рисунке выше, где каждая вершина раскрашена в белый (цвет 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 |
---|---|
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 |