This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long MX=5e5+10;
vector < int > mas[MX];
vector < int > lst;
void DFS(int zar,int mun)
{
if(mas[zar].size()==1)
{
lst.push_back(zar);
return;
}
for(auto u:mas[zar])
{
if(u!=mun)
{
DFS(u,zar);
}
}
return;
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
mas[a].push_back(b);
mas[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(mas[i].size()>1)
{
DFS(i,0);
break;
}
}
vector < pair < int , int > > ans;
int pol=lst.size()/2;
for(int i=0;i<pol;i++)
{
ans.push_back({lst[i],lst[i+pol]});
}
if(lst.size()%2)
{
ans.push_back({lst[0],lst.back()});
}
cout<<ans.size()<<"\n";
for(auto [a,b]:ans)
{
cout<<a<<" "<<b<<"\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |