次のようなアルゴリズムでも、正しい答えを得ることができます。

1. 適当な頂点を根として選び、DFS を行う。
2. DFS の行きがけ順もしくは帰りがけ順に頂点を並べた列を作り、\(A\) とする。
3. \(N\) が奇数ならば、重心を \(1\) つ選び \(A\) から削除する。
4. \((A _ i,A _ {i+\lfloor N/2\rfloor})\) を出力する。

これが正しいマッチングを与えることは、想定解の正当性の証明とほとんど同様にして行うことができます（重心を取り除いたときの連結成分が \(A\) において（ \(1\) つを除いて）区間になっていることを用います）。

適切に実装を行うことで、DFS を \(1\) 回だけ行ってこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<vector<unsigned>> edges(N);
    for (unsigned i{1}, u, v; i < N; ++i) {
        cin >> u >> v;
        edges[--u].emplace_back(--v);
        edges[v].emplace_back(u);
    }

    // 帰りがけ順の列が入る
    vector<unsigned> ans;
    ans.reserve(N);

    // dfs をして、
    //   1. 部分木のサイズを求める
    //   2. 帰りがけ順の列を作る
    [dfs{[N, &edges, &ans](auto &&f, unsigned now, unsigned prev) -> unsigned {
        // now_size := 自分とその子孫からなる部分木の大きさ
        // max_size := 自分を取り除いたときに残る部分木の大きさの最大値
        unsigned now_size{1}, max_size{};
        for (const auto &next: edges[now])
            if (next != prev) {
                const auto child_size{f(f, next, now)};
                now_size += child_size;
                max_size = max(max_size, child_size);
            }
        // 子ではない側の部分木の大きさは N - now_size
        max_size = max(max_size, N - now_size);
        // 重心でないか、N が偶数ならば列に追加
        if (N / 2 < max_size || N % 2 == 0)
            ans.emplace_back(now + 1);
        return now_size;
    }}]() {
        dfs(dfs, 0, 0);
    }();

    // ペアにして出力する
    for (unsigned i{}; i * 2 + 1 < N; ++i)
        cout << ans[i] << " " << ans[i + N / 2] << endl;
    return 0;
}