Вам дано простий зв’язний неорієнтований граф із \(N\) вершинами та \(M\) ребрами. (Граф називається простим, якщо в ньому немає мультиребер і самоциклів.) Для \(i = 1, 2, \ldots, M\), \(i\)-те ребро з’єднує вершини \(u_i\) і \(v_i\). Послідовність (\(A_1, A_2, \ldots, A_k\)) називають шляхом довжини \(k\), якщо задовольняються обидві наступні дві умови:

• Для всіх \(i = 1, 2, \dots, k\) виконується, що \(1 \leq A_i \leq N\).

• Для всіх \(i = 1, 2, \ldots, k-1\), вершини \(A_i\) і \(A_{i+1}\) безпосередньо з'єднані ребром.

Порожня послідовність розглядається як шлях довжиною 0.

Нехай \(S = s_1 s_2 \ldots s_N\) є рядком довжини \(N\), що складається з 0 і 1. Шлях \(A = (A_1, A_2, \ldots, A_k)\) вважається добрим шляхом щодо \(S\), якщо задовольняються наступні умови:

Для всіх \(i = 1, 2, \ldots, N\) виконується, що:

• якщо \(s_i = 0\), тоді \(A\) має парне число \(i\).

• якщо \(s_i = 1\), тоді \(A\) має непарну кількість \(i\).

Є \(2^N\) можливі \(S\) (іншими словами, є \(2^N\) рядки довжиною \(N\), що складаються з 0 і 1).

Знайдіть суму «довжин найкоротшого доброго шляху відносно S» за всіма цими \(S\).

Відповідно до обмежень цієї задачі можна довести, що для будь-якого рядка \(S\) довжини \(N\), що складається з 0 і 1, існує принаймні один добрий шлях щодо \(S\).

Обмеження

• \(2 \leq N \leq 17\)

• \(N-1 \leq M \leq \frac{N(N-1)}{2}\)

• \(1 \leq u_i, v_i \leq N\)

• Даний граф простий і зв'язний.

• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N, M\)

Наступні  \(M\) рядків містять цілі числа \(u_i, v_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь

Примітка

До прикладу 1:

• Для S = 000 порожня послідовність () є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 0.

• Для S = 100 (1) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 1.

• Для S = 010 (2) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 1.

• Для S = 110 (1, 2) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 2.

• Для S = 001 (3) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 1.

• Для S = 101 (1, 2, 3, 2) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 4.

• Для S = 011 (2, 3) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 2.

• Для S = 111 (1, 2, 3) є найкоротшим добрим шляхом відносно S, довжина якого дорівнює 3.

Отже, шукана відповідь: 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14

Приклад вхідних даних

3 2
1 2
2 3

Приклад вихідних даних

14

Приклад вхідних даних

5 5
4 2
2 3
1 3
2 1
1 5

Приклад вихідних даних

108