시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 74 13 9 17.647%

문제

Cactus란 그래프 상의 모든 에지가 최대 하나의 사이클에만 속한 연결된 양방향 그래프이다. 즉, Cactus는 몇몇 그래프를 포함하는 트리라고 생각하면 된다.

문제는 주어진 Cactus의 지름을 찾는 것이다. 지름이란 모든 두 점 사이의 최단 거리 중 최대 거리를 뜻한다.

위의 Cactus의 예에서는 6번 정점에서 12번 정점까지의 최단경로가 8로 이 두 점 사이의 최단 경로가 Cactus 내에 존재하는 최단경로 중 최대가 되므로 지름은 8이 된다.

입력

첫 줄에는 정점의 개수 N(1 ≤ N ≤ 50,000)과 간선의 집합 개수 M(0 ≤ M ≤ 10,000)이 주어진다. 다음 M개의 줄에 M개의 간선의 집합에 대한 정보가 주어지는데, 각 줄에 첫 번째 수 Ki(1 ≤ Ki ≤ 1,000)는 i번째 에지 집합의 개수를 나타낸다. 다음 Ki개의 수는 정점의 번호를 나타내는데 인접한 두 정점간의 에지가 집합에 포함되는 것을 의미한다.

출력

첫 줄에 Cactus의 지름을 출력한다.

예제 입력 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

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjExODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NTggXHVjOWMwXHViOTg0IiwiZGVzY3JpcHRpb24iOiI8cD5DYWN0dXNcdWI3ODAgXHVhZGY4XHViNzk4XHVkNTA0IFx1YzBjMVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNWQwXHVjOWMwXHVhYzAwIFx1Y2Q1Y1x1YjMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMGFjXHVjNzc0XHVkMDc0XHVjNWQwXHViOWNjIFx1YzE4ZFx1ZDU1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjNTkxXHViYzI5XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBDYWN0dXNcdWIyOTQgXHViYTg3XHViYTg3IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVkMmI4XHViOWFjXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzQgQ2FjdHVzXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5YzBcdWI5ODRcdWM3NzRcdWI3ODAgXHViYWE4XHViNGUwIFx1YjQ1MCBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjNzBcdWI5YWMgXHVjOTExIFx1Y2Q1Y1x1YjMwMCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC8yMDEwMDNcL2NjYy5KUEdcIiBzdHlsZT1cImhlaWdodDoyNTNweDsgd2lkdGg6MjQwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IENhY3R1c1x1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWNcdWIyOTQgNlx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgMTJcdWJjODggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1YWMwMCA4XHViODVjIFx1Yzc3NCBcdWI0NTAgXHVjODEwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVhYzAwIENhY3R1cyBcdWIwYjRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YmJjMFx1Yjg1YyBcdWM5YzBcdWI5ODRcdWM3NDAgOFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDUwLDAwMClcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzlkMVx1ZDU2OSBcdWFjMWNcdWMyMTggTSgwICZsZTsgTSAmbGU7IDEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgTVx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjOWQxXHVkNTY5XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4IEtpKDEgJmxlOyBLaSAmbGU7IDEsMDAwKVx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzVkMFx1YzljMCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViMmU0XHVjNzRjIEtpXHVhYzFjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NFx1YjM3MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YzgxNVx1YzgxMFx1YWMwNFx1Yzc1OCBcdWM1ZDBcdWM5YzBcdWFjMDAgXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgQ2FjdHVzXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhY3R1cyBSZWxvYWRlZCIsImRlc2NyaXB0aW9uIjoiPHA+Q2FjdHVzIGlzIGEgY29ubmVjdGVkIHVuZGlyZWN0ZWQgZ3JhcGggaW4gd2hpY2ggZXZlcnkgZWRnZSBsaWVzIG9uIGF0IG1vc3Qgb25lIHNpbXBsZSBjeWNsZS4gSW50dWl0aXZlbHkgY2FjdHVzIGlzIGEgZ2VuZXJhbGl6YXRpb24gb2YgYSB0cmVlIHdoZXJlIHNvbWUgY3ljbGVzIGFyZSBhbGxvd2VkLiBZb3VyIHRhc2sgaXMgdG8gXHVmYjAxbmQgYSBkaWFtZXRlciBvZiB0aGUgZ2l2ZW4gY2FjdHVzLiBEaWFtZXRlciBpcyB0aGUgbWF4aW1hbCBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHBhdGggYmV0d2VlbiBwYWlycyBvZiB2ZXJ0aWNlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDAzXC9jY2MuSlBHXCIgc3R5bGU9XCJoZWlnaHQ6MjUzcHg7IHdpZHRoOjI0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBvbiB0aGUgcGljdHVyZSBhYm92ZSB0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIHZlcnRpY2VzIDYgYW5kIDEyIGdvZXMgdGhyb3VnaCA4IGVkZ2VzIGFuZCBpdCBpcyB0aGUgbWF4aW1hbCBzaG9ydGVzdCBwYXRoIGluIHRoaXMgZ3JhcGgsIHRodXMgaXRzIGRpYW1ldGVyIGlzIDguPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0d28gaW50ZWdlciBudW1iZXJzIG4gYW5kIG0gKDEgJmxlOyBuICZsZTsgNTAgMDAwLCAwICZsZTsgbSAmbGU7IDEwIDAwMCkuIEhlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBncmFwaC4gVmVydGljZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBFZGdlcyBvZiB0aGUgZ3JhcGggYXJlIHJlcHJlc2VudGVkIGJ5IGEgc2V0IG9mIGVkZ2UtZGlzdGluY3QgcGF0aHMsIHdoZXJlIG0gaXMgdGhlIG51bWJlciBvZiBzdWNoIHBhdGhzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyBjb250YWlucyBhIHBhdGggaW4gdGhlIGdyYXBoLiBBIHBhdGggc3RhcnRzIHdpdGggYW4gaW50ZWdlciBudW1iZXIgazxzdWI+aTxcL3N1Yj4gKDIgJmxlOyBrPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIGZvbGxvd2VkIGJ5IGs8c3ViPmk8XC9zdWI+IGludGVnZXJzIGZyb20gMSB0byBuLiBUaGVzZSBrPHN1Yj5pPFwvc3ViPiBpbnRlZ2VycyByZXByZXNlbnQgdmVydGljZXMgb2YgYSBwYXRoLiBBZGphY2VudCB2ZXJ0aWNlcyBpbiBhIHBhdGggYXJlIGRpc3RpbmN0LiBQYXRoIGNhbiBnbyB0byB0aGUgc2FtZSB2ZXJ0ZXggbXVsdGlwbGUgdGltZXMsIGJ1dCBldmVyeSBlZGdlIGlzIHRyYXZlcnNlZCBleGFjdGx5IG9uY2UgaW4gdGhlIHdob2xlIGlucHV0IGZpbGUuIFRoZXJlIGFyZSBubyBtdWx0aWVkZ2VzIGluIHRoZSBncmFwaCAodGhlcmUgaXMgYXQgbW9zdCBvbmUgZWRnZSBiZXR3ZWVuIGFueSB0d28gdmVydGljZXMpLjxcL3A+XHJcblxyXG48cD5UaGUgZ3JhcGggaW4gdGhlIGlucHV0IGZpbGUgaXMgYSBjYWN0dXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdG8gdGhlIG91dHB1dCBmaWxlIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyICZtZGFzaDsgdGhlIGRpYW1ldGVyIG9mIHRoZSBnaXZlbiBjYWN0dXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d