Перезавантаження кактуса#7586

Перезавантаження кактуса

1 секунда

128 мегабайтів

Легка

Кактус — це зв'язний неорієнтований граф, в якому кожне ребро належить не більше ніж одному простому циклу. Інтуїтивно кактус є узагальненням дерева, в якому дозволені деякі цикли. Ваше завдання — знайти діаметр заданого кактуса. Діаметр — це максимальна довжина найкоротшого шляху між парами вершин.

У наведеному кактусі найкоротша відстань між вершинами $6$ і $12$ проходить через $8$ ребер і є найбільшим найкоротшим шляхом у графі, тому його діаметр дорівнює $8$ .

Вхідні дані

Перший рядок містить числа $n$ і $m$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000, $0 \leq m \leq 10000$ 0 \leq m \leq 10000). Тут $n$ — кількість вершин у графі. Вершини пронумеровані від $1$ до $n$ . Ребра задані множиною реберно-непересічних шляхів, де $m$ — число таких шляхів.

Кожен із наступних $m$ рядків містить шлях у графі. Шлях починається числом $k_{i}$ k_i ( $2 \leq k_{i} \leq 1000$ 2 \leq k_i \leq 1000), за яким йдуть $k_{i}$ k_i цілих чисел від $1$ до $n$ . Ці $k_{i}$ k_i числа представляють вершини графа в шляху. Сусідні вершини в шляху різні. Шлях може проходити через одну вершину декілька разів, однак кожне ребро зустрічається лише один раз. Мультиребра в графі відсутні (між будь-якими двома вершинами існує не більше одного ребра).

Граф у прикладі є кактусом.

Вихідні дані

Вивести одне число — діаметр кактуса.

Приклади

Приклад

12 6
3 1 2 3
3 2 4 5
9 6 7 8 4 3 9 10 11 12
2 8 5
2 9 2
2 6 12

Приклад 1