Дивне Забарвлення

Вам дано неорієнтований граф G. Потрібно пофарбувати ребра графа G кольорами 0, 1, 2, ... так, щоб:

1. Сума кольорів усіх ребер була мінімальною.

2. Для кожного ребра з кольором 0 має існувати суміжне ребро, колір якого 2. Два ребра вважаються суміжними, якщо вони мають спільну вершину.

Вхідні дані

Перша строка вхідних даних містить кількість тестів.

Для кожного тесту спочатку задано 1 ≤ n ≤ 20 та 1 ≤ m ≤ 30, де n — кількість вершин, а m — кількість ребер. У наступних m рядках кожен рядок містить дві кінцеві точки ребра.

Вихідні дані

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

Приклади