У Анади есть комплект домино. Каждое домино разделено на две части, на каждой части нарисовано сколько-то точек. Для каждой такой пары \(a\) и \(b\), что \(1 \leq a \leq b \leq 6\), есть ровно одно домино с \(a\) точками на одной половине и \(b\) точками на другой половине. Комплект состоит ровно из \(21\) домино. Вот иллюстрация всех домино из набора:
А также у Анади есть граф без петель и кратных ребер. Он хочет выбрать некоторые домино и поставить их на ребра графа. Когда он ставит домино на ребро, он также выбирает его направления. Иначе говоря, одна половинка домино должна быть направлена в сторону одного конца ребра, а другая половинка в сторону другого конца ребра. На каждое ребро можно поставить не более одного домино. Необязательно ставить домино на все ребра графа.
Но также есть одно дополнительно условие: если несколько половинок домино направлены к одной и той же вершине, все эти половинки должны содержать одинаковое число точек.
Какое максимальное количество домино Анади может расставить на ребрах графа?
Выходные данные
Выведите одно целое число — максимальное количество домино, которое Анади может расставить на ребрах графа.
Примечание
Иллюстрация к графу Анади из первого примера:
А вот один из способов расставить на его ребрах домино:
Обратите внимание, что к каждой вершине направлены половинки домино с одинаковым числом точек. Например, все половинки направленные к вершины \(1\) содержат три точки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
2 3
3 4
4 1
|
4
|
|
2
|
7 0
|
0
|
|
3
|
3 1
1 3
|
1
|
|
4
|
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
|