У Анади есть комплект домино. Каждое домино разделено на две части, на каждой части нарисовано сколько-то точек. Для каждой такой пары $$$a$$$ и $$$b$$$, что $$$1 \leq a \leq b \leq 6$$$, есть ровно одно домино с $$$a$$$ точками на одной половине и $$$b$$$ точками на другой половине. Комплект состоит ровно из $$$21$$$ домино. Вот иллюстрация всех домино из набора:
А также у Анади есть граф без петель и кратных ребер. Он хочет выбрать некоторые домино и поставить их на ребра графа. Когда он ставит домино на ребро, он также выбирает его направления. Иначе говоря, одна половинка домино должна быть направлена в сторону одного конца ребра, а другая половинка в сторону другого конца ребра. На каждое ребро можно поставить не более одного домино. Необязательно ставить домино на все ребра графа.
Но также есть одно дополнительно условие: если несколько половинок домино направлены к одной и той же вершине, все эти половинки должны содержать одинаковое число точек.
Какое максимальное количество домино Анади может расставить на ребрах графа?
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 7$$$, $$$0 \leq m \leq \frac{n\cdot(n-1)}{2}$$$) — количество вершин и ребер графа.
В каждой из следующих $$$m$$$ строк записано по два целых числа. Числа в $$$i$$$-й строке это $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$), описывающих ребро в графе, соединяющее вершины $$$a_i$$$ и $$$b_i$$$.
Гарантируется, что никакое ребро не соединяет вершину саму с собой, а также между каждой парой вершин есть не более одного ребра.
Выведите одно целое число — максимальное количество домино, которое Анади может расставить на ребрах графа.
4 4 1 2 2 3 3 4 4 1
4
7 0
0
3 1 1 3
1
7 21 1 2 1 3 1 4 1 5 1 6 1 7 2 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 5 4 6 4 7 5 6 5 7 6 7
16
Иллюстрация к графу Анади из первого примера:
А вот один из способов расставить на его ребрах домино:
Обратите внимание, что к каждой вершине направлены половинки домино с одинаковым числом точек. Например, все половинки направленные к вершины $$$1$$$ содержат три точки.
