Submission #1343931

#TimeUsernameProblemLanguageResultExecution timeMemory
1343931teodorazvanNetwork (BOI15_net)C++20
100 / 100
467 ms47304 KiB
#include <bits/stdc++.h>

using namespace std;

int n;

vector<vector<int>> a;
vector<int>gr,frunz;

void dfs(int nod,int rad) {
    bool frun=true;
    for (auto f:a[nod]) {
        if (f==rad) continue;
        frun=false;
        dfs(f,nod);
    }
    if (frun)  frunz.push_back(nod);
}

int main() {
    cin>>n;
    a.resize(n+1);
    gr.resize(n+1);
    int x,y;
    for (int i=1;i<n;i++) {
        cin>>x>>y;
        gr[x]++;
        gr[y]++;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i=1;i<=n;i++) {
        if (gr[i]>1) {
            dfs(i,0);
            break;
        }
    }
    int cf=frunz.size(),ans=(cf+1)/2,skip=cf/2;
    cout<<ans<<'\n';
    for (int i=0;i<ans;i++) cout<<frunz[i]<<" "<<frunz[(i+skip)%cf]<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...