Etäisyydet

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

void solve() {
	int n;
	cin >> n;

	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	vector<int> dep(n);
	function<void(int, int)> dfs1 = [&](int s, int e) {
		for (auto& u : g[s]) {
			if (u == e) continue;
			dep[u] = dep[s] + 1;
			dfs1(u, s);
		}
	};
	dfs1(0, 0);

	vector<int> vis(n);
	function<void(int)> dfs2 = [&](int s) {
		cout << s + 1 << " ";
		vis[s] = 1;
		function<pair<int, int>(int, int, int)> dfs3 = [&](int s, int e, int d) -> pair<int, int> {
			pair<int, int> ret{dep[s], s};
			if (vis[s]) ret.first = -1;
			if (d == 0) return ret;
			for (auto& u : g[s]) {
				if (u == e) continue;
				ret = max(ret, dfs3(u, s, d - 1));
			}
			return ret;
		};
		auto [d, u] = dfs3(s, s, 3);
		if (d == -1) return;
		dfs2(u);
	};
	dfs2(0);
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) solve();
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED