Question
Clans of the Great Valley
Across a large region, there are n villages. Among these villages, m two-way roads exist. Each road connects exactly two villages and represents an alliance between them.
Your task is to find and print all clans in the region.
A clan is a group of villages such that every village in that group can be reached from any other village using the alliance roads, either through a direct road or by passing through other allied villages.
Input
The first line contains two integers, n and m, representing the number of villages and the number of two-way roads respectively.
The next m lines each contain two integers u and v, meaning village u and village v share an alliance.
The next m lines each contain two integers u and v, meaning village u and village v share an alliance.
Output
Print all clans in the region, where each clan is a list of villages that belong to the same connected group.
Each clan should be printed on a new line.
The order of the clans and the order of villages inside each clan does not matter.
Each clan should be printed on a new line.
The order of the clans and the order of villages inside each clan does not matter.
Example
Input:
7 4
0 1
2 3
3 4
5 6
Output:
0 1
2 3 4
5 6
Explanation:
The region has 7 villages numbered from 0 to 6.
The alliance roads connect the following villages:
7 4
0 1
2 3
3 4
5 6
Output:
0 1
2 3 4
5 6
Explanation:
The region has 7 villages numbered from 0 to 6.
The alliance roads connect the following villages:
- Villages 0 and 1 are connected to each other, so they form one clan.
- Villages 2, 3, and 4 are linked through the roads (2–3) and (3–4). Since each of them can be reached from the others, they form another clan.
- Villages 5 and 6 are connected to each other, forming the third clan.