There are n people numbered 1 to n and m friendships (each connects two people, in both directions). A group is a set of people connected directly or through friends. Print the number of groups.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ m ≤ 200000
Input and output
- Input
- Line 1: n m Next m lines: u v
- Output
- One integer: the number of groups.
Examples
Input 1
5 3
1 2
2 3
4 5Output
2Two groups.
Input 2
3 0Output
3No friendships.
Show hints
- Start a search from every person not seen yet.
- Or merge sets with union-find.
Show the explanation
Union-find: start with n groups; for every edge whose ends are in different sets, merge them and subtract one. With path compression and union by size this is nearly O(n + m). A DFS/BFS from every unvisited node also works in O(n + m); use an explicit stack to avoid recursion limits on long chains.
Original UniCircle question. Last reviewed 21 Oct 2026.