Циклы рядков
Каждая из M дорожек Парка Политехнического университета Бухареста соединяет два из N перекрестков парка (пронумерованных от 1 до N). Между любой парой перекрестков не может быть более одной дорожки, и можно добраться от любого перекрестка до любого другого, следуя по одной или нескольким дорожкам. Цикл дорожек называется простым, если он проходит через каждый из своих перекрестков ровно один раз.
Администрация университета хочет разместить фотографии победителей Регионального студенческого конкурса по программированию на дорожках таким образом, чтобы фотографии победителей из одного университета находились на дорожках одного и того же простого цикла. Поэтому они стремятся назначить самые длинные простые циклы дорожек наиболее успешным университетам. Вопрос в том, как найти самые длинные циклы? К счастью, выясняется, что каждая дорожка парка участвует не более чем в одном простом цикле (см. рисунок).
В первой строке входного файла указано число T тестовых случаев. Каждый тестовый случай начинается со строки с двумя положительными целыми числами N и M, разделенными пробелом (4 <= N <= 4444). Каждая из следующих M строк тестового случая содержит метки одной из пар перекрестков, соединенных дорожкой.
Для каждого тестового случая выведите в одной строке длину максимального простого цикла.