Distances

#include <bits/stdc++.h>
 
#define ll long long
#define what_is(a) cout << #a << " is " << a << "\n";
#define check(a) cout << "reached " << a << "\n";
 
using namespace std;
 
vector<int> ans;
 
void dfs(int n,int d,vector<vector<int>> &adjList,int* v){
	bool flag = false;
	//check(n+1)
	//what_is(d)
	if(d==2){
		v[n]=1;
		ans.push_back(n);
	}
 
	
	for(int x:adjList[n]){
		if(v[x])continue;
		if(d==1){
			flag = true;
			dfs(x,2,adjList,v);
		}else{
			dfs(x,1,adjList,v);
		}
	}
 
	for(int x:adjList[n]){
		if(v[x]&&d==1)continue;
		if(d==1){
			flag = true;
			dfs(x,2,adjList,v);
		}else{
			dfs(x,1,adjList,v);
		}
	}
	if(!flag && d==1 && v[n]==0)
	dfs(n,2,adjList,v);
}
 
void solve(int T){
	ans = vector<int>();
	int n;
	cin >> n;
	vector<vector<int>> adjList(n,vector<int>());
	for(int i=0;i<n-1;i++){
		int x,y;
		cin >> x >> y;
		x--,y--;
		adjList.at(x).push_back(y);
		adjList.at(y).push_back(x);
	}
	int leaf =0;
	for(int i=0;i<n;i++)if(adjList.at(i).size()==1)leaf = i;
	int v[n];
	memset(v,0,sizeof(v));
	//what_is(leaf)
	dfs(leaf,2,adjList,v);
	for(int u:ans)cout << u+1 << " ";
	cout << "\n";
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	while(t--)
	solve(t);
}
 
/*
 1
 7
 1 2
 2 3
 3 4
 2 5
 5 6
 5 7
  */

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER