선인장 그래프의 지름

시간 제한1초메모리 제한128 MB

요약
모든 간선이 최대 하나의 단순 사이클에 속하는 선인장 그래프에서 두 정점 사이의 최단 거리 중 최댓값(지름)을 구합니다.
난이도

어려움10점 중 9점

유형
그래프, DFS, 트리, 동적 계획법
정답자
아직 제출이 없습니다

문제

선인장 그래프는 모든 간선이 많아야 하나의 단순 사이클에만 속하는 연결된 무방향 그래프이다. 여러 경로와 사이클이 트리처럼 붙어 있는 그래프로 생각할 수 있다.

그래프의 지름은 모든 두 정점 사이의 최단 거리 중 최댓값이다. 주어진 선인장 그래프의 지름을 구하라.

입력

첫째 줄에 정점의 개수 N (1 <= N <= 50,000)과 간선 집합의 개수 M (0 <= M <= 10,000)이 주어진다.

다음 M개의 줄에는 각각 하나의 간선 집합 정보가 주어진다. 각 줄의 첫 번째 정수 K_i (1 <= K_i <= 1,000)는 그 줄에 주어지는 정점 번호의 개수이다. 이어서 K_i개의 정점 번호 v_1, v_2, ..., v_{K_i}가 주어진다. 이 정점 번호열에서 서로 인접한 두 정점 사이의 간선이 그래프에 포함된다.

입력으로 주어지는 그래프는 선인장 그래프이다.

출력

선인장 그래프의 지름을 출력한다.

예제1

  1. 예제 1

    입력
    15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
    예상 출력
    8