Java/Python/C++ Графы, количество разных маршрутов

1) Написать программу на одном из перечисленных языков программирования: Java / Python / C++

2) ТЗ:

Каждый маршрут посетит ровно четыре достопримечательности. Достопримечательность - озеро(LAKE) или водопад(WATERFALL) на холмах. Маршрут начнется с LAKE, затем продолжится до WATERFALL, затем перейдет к другому LAKE, затем к другому WATERFALL и, наконец, вернется к LAKE, с которого он начинался.

Дана схема путей, соединяющее точки путей "интересных мест в парке".  Найти максимальное возможное кол-во путей.  Два маршрута считаются разными, если есть хотя бы одно место, которое является частью одного маршрута и не является частью другого маршрута, или если маршруты посещают одно и то же место в другом порядке.

Пример: a)

Input

8 12

0 1

0 5

1 5

1 4

5 4

5 6

1 2

4 2

4 6

2 6

2 3

7 6

0 L

4 L

2 L

3 L

1 W

5 W

7 W

6 W

Output 8

Input:

1 строка M N, M - кол-во мест N - кол-во путей

2-13 строки - связи между местами

14+ строки - L - Lake W-Waterfall

Output - максимальное кол-во возможный путей

успешно выполненной работой считается:

1) правильные результаты (файлы с числами будут предоставлены лично)

2) оптимизированная программа, должна пройти тест по времени выполнения программы на специальном сайте