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<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
using namespace std;
const int MAX_N=1e5+5;
int n;
vector<int>g[MAX_N];
int ans[MAX_N];
int all;
bool dfs(int u,int par)
{
bool nowswapped=0;
for(int v:g[u])
{
if(v==par)continue;
bool swapped=dfs(v,u);
if(swapped)continue;
swap(ans[v],ans[u]);
all+=2;
nowswapped=1;
}
if(nowswapped+par==0)
{
swap(ans[u],ans[g[u][0]]);
all+=2;
nowswapped=1;
}
return nowswapped;
}
signed main()
{
cin>>n;
ans[n]=n;
for(int i=1;i<n;i++)
{
ans[i]=i;
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<all<<" "<<0<<"\n";
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
cout<<1<<" ";
}
cout<<"\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... |