Remove Cycles in an Undirected Graph

You are given an undirected graph with ( n ) vertices and ( m ) edges. The vertices are labeled from 0 to ( n-1 ). Your task is to remove all cycles from the graph by selecting a subset of the edges that form a spanning tree.

A spanning tree is a subset of the edges that connects all the vertices without any cycles. You may use the Union-Find (disjoint set union) algorithm to achieve this. If there are multiple valid spanning trees, output any one of them.

inputFormat

The first line contains two integers ( n ) and ( m ), representing the number of vertices and edges respectively. The following ( m ) lines each contain two integers ( u ) and ( v ) (separated by a space) that represent an undirected edge connecting vertices ( u ) and ( v ).

outputFormat

Output the edges that form the spanning tree. Each edge should be printed on a separate line in the format: u v. The order of the edges does not matter as long as the printed edges form a valid spanning tree.## sample

5 6
0 1
0 2
1 2
1 3
2 4
3 4

0 1
0 2
1 3
2 4