Spanning tree with max degree

You are given an undirected unweighted connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the maximum degree over all vertices is maximum possible. Recall that the degree of a vertex is the number of edges incident to it.

Input
The first line contains two integers n and m (2 ≤ n ≤ 2x10^5, n−1 ≤ m ≤ min(2x10^5,n n−1)2)) — the number of vertices and edges, respectively. The following m lines denote edges: edge i is represented by a pair of integers vi, ui (1≤ vi,ui ≤n, ui≠vi), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair (vi,ui) there are no other pairs (vi,ui) or (ui,vi) in the list of edges, and for each pair (vi,ui) the condition vi≠ui is satisfied.

Output
Print n−1 lines describing the edges of a spanning tree such that the maximum degree over all vertices is maximum possible. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge (v,u) is considered the same as the edge (u,v)).

If there are multiple possible answers, print any of them.

Examples

1. input
5 5
1 2
2 3
3 5
4 3
1 5

output
3 5
2 1
3 2
3 4

2. input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

output
4 1
1 2
1 3


3. input
8 9
1 2
2 3
2 5
1 6
3 4
6 5
4 5
2 7
5 8

output
3 2
2 5
8 5
6 1
2 7
1 2
3 4

--------------------------------------------------------------------------------------------------------------------------------------
THOUGHT PROCESS

You just need to remove unnecessary edges to form a spanning tree, keeping this in mind that the current highest indegree vertex must not lose any edge that might reduce its indegree. Second thing to take care of is that no spanning tree will have cycles, as tree do not have cycles in them, so while joining edges make sure they are not making any cycles. This can be done by using DSU or BFS, BFS being the straightforward answer.

--------------------------------------------------------------------------------------------------------------------------------------


#include<bits/stdc++.h>
using namespace std;

vector<int> adj[200005];
bool vis[200005];
int indegree[200005];

void LET_IT_RIP(int n){
   queue<int> q;
   int mxDegree=0;
   for(int i=1;i<=n;i++){
      mxDegree=max(mxDegree,indegree[i]);
   }
   for(int i=1;i<=n;i++){
      if(indegree[i]==mxDegree){
         q.push(i);
         vis[i]=true;
         break;
      }
   }
   while(!q.empty()){
      int size=q.size();
      while(size--){
         int node=q.front();
         q.pop();
         for(auto nei: adj[node]){
            if(vis[nei]==false){
               q.push(nei);
               vis[nei]=true;
               cout<<node<<" "<<nei<<endl;
            }
         }
      }
   }
}

int main(){
   memset(vis,false,sizeof(vis));
   memset(indegree,0,sizeof(indegree));
   int n,m;
   cin>>n>>m;
   for(int i=0;i<m;i++){
      int u,v;
      cin>>u>>v;
      indegree[u]++;
      indegree[v]++;
      adj[u].push_back(v);
      adj[v].push_back(u);
   }
   LET_IT_RIP(n);
}


Example three graph->
       7
       |
       |
1------2------3------4
|      |  ___________|
|      | /
6------5-------------8


Spanning tree becomes->
       7
       |
       |
1------2------3------4
       |
       |
6------5-------------8