도메인 클러스터

인터넷의 도메인이 서로 어떻게 이어지는지 분석한다. 도메인은 URL에서 / 앞에 오는 부분이다. twitter.com, aipo.computing.dcu.ie, google.com이 도메인의 예다.

도메인 d1에서 d2로 가는 링크가 있으면 d1은 d2에 연결되어 있다. 또 d1이 d3에 연결되어 있고 d3이 d2에 연결되어 있으면 d1은 d2에 연결되어 있다. 모든 도메인은 자기 자신에 연결되어 있다고 본다.

아래 그림은 도메인 다섯 개로 이루어진 구조다. 링크는 D1에서 D2, D1에서 D4, D2에서 D3, D3에서 D2, D3에서 D4, D3에서 D5, D5에서 D2로 이어진다.

• D1은 D2, D3(D2를 거쳐), D4, D5(D3을 거쳐)에 연결되어 있다.
• D2는 D3, D4(D3을 거쳐), D5(D3을 거쳐)에 연결되어 있다.
• D3은 D2, D4, D5에 연결되어 있다.
• D4는 다른 어떤 도메인에도 연결되어 있지 않다.
• D5는 D2, D3(D2를 거쳐), D4(D3을 거쳐)에 연결되어 있다.

집합 $S$에 속한 모든 도메인이 $S$의 나머지 모든 도메인에 연결되어 있을 때, 가장 큰 $S$를 찾고 싶다. 위 구조에서 이 조건을 만족하는 집합은 다음과 같다.

• {D1}: 자기 자신에 연결되어 있다.
• {D2, D3, D5}: D2에서 D3과 D5로 갈 수 있고, D3에서 D2와 D5로 갈 수 있고, D5에서 D2와 D3으로 갈 수 있다.
• {D4}: 자기 자신에 연결되어 있다.

인터넷의 링크가 주어지면 가장 큰 집합의 크기를 구하라.

첫째 줄에 도메인의 개수 $D$가 주어진다. 도메인의 이름은 $1$부터 $D$까지의 정수다. ($1 \le D \le 5000$)

둘째 줄에 도메인 사이 링크의 개수 $L$이 주어진다. 이어지는 $L$개의 줄에는 각각 두 정수가 주어진다. 첫 번째 정수는 링크의 출발 도메인이고, 두 번째 정수는 도착 도메인이다. A에서 B로 가는 링크가 있어도 B에서 A로 가는 링크가 있다는 뜻은 아니며, 모든 도메인은 명시적인 링크 없이도 자기 자신에 연결되어 있다. 같은 링크는 두 번 이상 주어지지 않는다. ($0 \le L \le D^2$)

위 조건을 만족하는 가장 큰 도메인 집합의 크기를 출력한다. 크기가 가장 큰 집합이 둘 이상이어도 그 크기 하나만 출력한다.