Wires to Add

Difficulty: 1300 4000 ms 128 MB

graphs

What is the minimum number of new links needed so that everyone ends up in a single circle?

Input: the first line has N and M; each of the next M lines has an edge u v (1-based).

Output: components − 1.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

5 2
1 2
3 4

2

1 0

0

Read the Editorial