Цикли Рядків
Кожна з M доріжок Парку Політехнічного університету Бухареста з'єднує дві з N перехресть парку (позначені від 1 до N). Жодна пара перехресть не з'єднана більше ніж однією доріжкою, і можна дістатися від кожного перехрестя до будь-якого іншого, використовуючи одну або більше доріжок. Цикл доріжок є простим, якщо він проходить через кожне з його перехресть рівно один раз.
Адміністрація університету хоче розмістити фотографії переможців Регіонального студентського конкурсу з програмування на доріжках так, щоб фотографії переможців з одного університету були на доріжках одного простого циклу. Тому адміністрація прагне призначити найдовші прості цикли доріжок найуспішнішим університетам. Завдання полягає у визначенні найдовших циклів. На щастя, кожна доріжка парку бере участь не більше ніж в одному простому циклі (див. малюнок).
У першому рядку вхідного файлу вказано число T тестових випадків. Кожен тестовий випадок починається з рядка з позитивними цілими числами N та M, розділеними пробілом (4 <= N <= 4444). Кожен з наступних M рядків тестового випадку містить позначки однієї з пар перехресть, з'єднаних доріжкою.
Для кожного з тестових випадків, в одному рядку виходу, виведіть довжину максимального простого циклу.