A guild has n members numbered 1 through n. Some pairs of members sign a mutual pact. An alliance is a maximal set of members connected directly or indirectly through pacts. A member who signed no pacts forms an alliance of size one.
Report the size of the largest alliance.
Line 1: two integers n and m.
Next m lines: two integers u and v, a pact between members u and v. A pact may be listed more than once; a pact never joins a member to themselves.
A single integer: the number of members in the largest alliance.
Example 1
Input
6 3 1 2 2 3 4 5
Expected
3
Explanation
Alliances are {1,2,3} (size 3), {4,5} (size 2), and {6} (size 1). The largest has 3 members.
Example 2
Input
4 0
Expected
1
Explanation
No pacts exist, so every member is a size-1 alliance; the largest size is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →