e-olymp
Competitions

Міська олімпіада м. Дніпра (ІІ етап, 2017-18 навч.рік)

Браслети (Bangles)

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з'єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося N різних типів замків (позначимо їх номерами від 1 до N) і М типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа N (кількість типів замків) та M (кількість типів деталей). (4 ≤ N ≤ 300). У M наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів. 112.jpg

Time limit 0.9 second
Memory limit 64 MiB
Input example #1
5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5
Output example #1
2

Example description: Існує два варіанти з’єднання: (3,4) – (4,2) – (2,5) – (5,3) та (1,4) – (4,5) – (5,3) – (3,1) У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

Source ХХХІ олімпіада м. Дніпро (ІІ етап)