시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 180 | 112 | 96 | 66.667% |
We are analyzing how the domains on the Internet connect to each other. A domain is the part of a URL that comes before the / character. Examples of domains are: twitter.com, aipo.computing.dcu.ieor google.com. A domain d1 is connected to a domain d2 if there is a link from d1 to d2 or if d1 is connected to a domain d3 and d3 is connected to d2. We consider that a domain is connected to itself. In the following structure of domains:
We want to obtain the biggest subset of domains S where each domain in S is connected to all the other domains in S. In the example above we have the following subsets that meet this criteria:
Please, given the links of the Internet, compute the size of the biggest subset.
The first line will contain an integer D representing the number of domains. The names of the domains will be integers from 1 to D. (1 ≤ D ≤ 5000)
The second line will contain an integer L representing the number of links between domains. The following L lines will contain two integers each. The first integer is the source of the link and the second is the destination. Remember that a link from A to B does not imply a link from B to A and that every domain is connected to itself without the need of an explicit link. No link will appear more than once. (0 ≤ L ≤ D2)
The size of the biggest subset of domains that meet the criteria above. If two or more subsets are tied for the biggest size, print the size of any of them.
5 7 1 2 1 4 2 3 3 4 3 2 3 5 5 2
3
4 4 1 2 4 1 3 4 2 3
4