Странная Раскраска

Вам дан неориентированный граф G. Ваша задача — раскрасить рёбра графа G цветами 0, 1, 2 и так далее, при этом соблюдая следующие условия:

1. Сумма всех цветов рёбер должна быть минимальной.

2. Для каждого ребра, окрашенного в цвет 0, должно существовать смежное ребро, окрашенное в цвет 2. Два рёбра считаются смежными, если они имеют общую вершину.

Входные данные

Первая строка входных данных содержит количество тестов.

Для каждого теста сначала указаны 1 ≤ n ≤ 20 и 1 ≤ m ≤ 30, где n — количество вершин, а m — количество рёбер. В следующих m строках каждая строка содержит две конечные точки ребра.

Выходные данные

Для каждого теста выведите минимальную сумму цветов рёбер, удовлетворяющих указанным условиям.

Примеры