← 返回 amazon 的题目列表Merge Products into Categories (Union-Find / Connected Components)
类型：online_judge
You are given m pairs (a, b) indicating that products a and b belong to the same category. The relation is transitive: if a is grouped with b and b with c, then a is grouped with c.
Compute:
The final number of categories (number of connected components).
The size of each category (number of products in each component). Output the sizes sorted increasingly.
Input (stdin)
First line: integer m, the number of pairs.
Next m lines: two strings a b.
Output (stdout)
First line: the number of categories.
Second line: component sizes in increasing order, separated by spaces.
Constraints
1 <= m <= 2*10^5
Product IDs are non-empty strings of length <= 30
Duplicate pairs may appear.
Example Input:
4
a b
b c
d e
f g
Output:
3
2 2 3
Example
Input
4
a b
b c
d e
f g
Output
3
2 2 3