Перезавантаження кактуса
Кактус — це зв'язний неорієнтований граф, у якому кожне ребро належить не більше ніж одному циклу. Інтуїтивно, кактус є узагальненням дерева, в якому дозволені деякі цикли. Ваше завдання — знайти діаметр заданого кактуса.
У наведеному кактусі найкоротша відстань між вершинами 6 і 12 проходить через 8 ребер і є найбільшим найкоротшим шляхом у графі, тому його діаметр дорівнює 8.
Вхідні дані
Перший рядок містить числа n і m (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000). Тут n — кількість вершин у графі. Вершини пронумеровані від 1 до n. Ребра задані множиною реберно-неперетинних шляхів, де m — кількість таких шляхів.
Кожен з наступних m рядків містить шлях у графі. Шлях починається числом k[i] (2 ≤ k[i] ≤ 1000), за яким слідують k[i] цілих чисел від 1 до n. Ці k[i] числа представляють вершини графа в шляху. Сусідні вершини в шляху різні. Шлях може проходити через одну вершину кілька разів, проте кожне ребро зустрічається тільки один раз. Мультиребра в графі відсутні (між будь-якими двома вершинами існує не більше одного ребра).
Граф у прикладі є кактусом.
Вихідні дані
Виведіть одне число — діаметр кактуса.