Submission #3194170

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define lowbit(p) (p&(-p))
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define A first
#define B second
using namespace std;
void read(int &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void read(ll &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void Min(int &x,int y){
	if (x>y)x=y;
}
void Max(int &x,int y){
	if (x<y)x=y;
}
void Min(ll &x,ll y){
	if (x>y)x=y;
}
void Max(ll &x,ll y){
	if (x<y)x=y;
}

#define M 100005
struct ed{
	int x,nx;
}e[M<<1];
int fa[M],nx[M],ecnt=1,n,mx,id,val[M],Q[M],tot;
bool mark[M];
void add(int x,int y){
	e[ecnt]=(ed){y,nx[x]};
	nx[x]=ecnt++;
}
void dfs(int f,int x,int d){	
	fa[x]=f;
//	printf("%d->%d\n",f,x);
	if (d>mx){
		mx=d;
		id=x;
	}
	for (int i=nx[x];i;i=e[i].nx)if (e[i].x!=f){
		dfs(x,e[i].x,d+1);
	}
}
int qu(int x){
	int res=0,i,j,y;
	for (i=nx[x];i;i=e[i].nx)if (!mark[e[i].x]){
		y=e[i].x;
		for (j=nx[y];j;j=e[j].nx)if (e[j].x!=x){
			return -1;
		}	
		res++;
	}
	return res;
}
void chk(){
	mx=0;
	int tmp,i,j,x;
	dfs(0,1,0);
//	printf("id=%d\n",id);
	mx=0;
	dfs(0,id,0);
//	printf("id=%d\n",id);
	for (x=id;x;x=fa[x]){
//		printf("%d ",x);
		Q[++tot]=x;
		mark[x]=1;
//		printf("fa[%d]=%d\n",x,fa[x]);
	}
//	printf("\n");
	for (i=1;i<=tot;i++){
		tmp=qu(Q[i]);
		if (tmp==-1){
			printf("-1\n");
			exit(0);
		}
		else {
			val[i]=tmp;
		}
	}
	for (i=1;i<=tot;i++){
		if (val[i]!=val[tot-i+1]){
			if (val[i]<val[tot-i+1]){
				return ;
			}
			else{
				for (j=1;j<=tot-j+1;j++){
					swap(Q[j],Q[tot-j+1]);
					swap(val[j],val[tot-j+1]);
				}
				return ;
			}
		}
	}
}
void pt(){
	int now=0,i,l,r;
	for (i=1;i<=tot;i++){
		l=now+2; r=now+val[i]+1;
		for (int x=l;x<=r;x++){
			printf("%d ",x);
		}
		printf("%d ",now+1);
		now=r;
	}
	printf("\n");
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen("1.in","r",stdin);
	read(n);
	int i,x,y;
	for (i=1;i<n;i++){
		read(x); read(y);
		add(x,y);
		add(y,x);	
	}
	chk();
	pt();
	return 0;
}

Submission Info

Judge Result