Submission #19310138

---

Source Code Expand

//const int N = 1e5+5;
//int depth[N];
//vi adj[N];
//void dfs(int u, int p){
//    for(int v : adj[u])
//        if(v != p){
//            depth[v] = depth[u]+1;
//            dfs(v,u);
//        }
//}
//void __(){
//    _(int,n);
//    _(vpii,edges,n-1);
//    if(n == 2){
//        print 1,2;
//        return;
//    }
//    vi deg(n+1);
//    for(auto _ : edges)
//        ++deg[_.X],++deg[_.Y];
//    vpii nle;
//    for(auto _ : edges){
//        int u,v;
//        tie(u,v) = _;
//        if(deg[u] > 1 && deg[v] > 1)
//            nle.pb({u,v});
//        adj[u].pb(v);
//        adj[v].pb(u);
//
//    }
//    map<int,int> cnt;
//    for(auto _ : nle){
//        cnt[_.X]++;
//        cnt[_.Y]++;
//    }
//    vi ends;
//    for(auto _ : cnt)
//        if(_.Y == 1)
//            ends.pb(_.X);
//    if(sz(ends) > 2){
//        print -1;
//        return;
//    }
//    int root = 1;
//    while(deg[root] == 1)
//        ++root;
//    if(!ends.empty())
//        root = ends[0];
//    dfs(root,-1);
//    vpii sorted;
//    rep(i,1,n)
//        if(deg[i] > 1)
//            sorted.pb({depth[i],i});
//    sort(all(sorted));
//    vi arr;
//    for(auto _ : sorted){
//        int u = _.Y;
//        int cur = 0;
//        for(int v : adj[u])
//            if(deg[v] == 1)
//                ++cur;
//        arr.pb(cur);
//    }
//    assert(arr[0] > 0);
//    arr.insert(arr.begin(),0);
//    arr[1]--;
//    assert(arr.back() > 0);
//    arr.back()--;
//    arr.pb(0);
//    {
//        vi test = arr;
//        reverse(all(test));
//        if(test < arr)
//            arr = test;
//    }
//    vi ans;
//    int nxt = 1;
//    for(int x : arr){
//        rep(i,x)
//            ans.pb(nxt+1+i);
//        ans.pb(nxt);
//        nxt += x+1;
//    }
//    print ans;
//}
//
#include <map>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_INT(i,l,r) for(int i = (l); i <= (r); ++i)
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define X first
#define Y second
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

T1 ostream& operator<<(ostream& stream, const vector<T>& t);
template <typename F, typename S> static
istream& operator>>(istream& stream, pair<F, S>& t){
    return stream >> t.first >> t.second;
}
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout) 
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }

    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
T1 ostream& operator<<(ostream& stream, const vector<T>& t){
    for(int i = 0; i < sz(t); ++i){
        stream << t[i];
        if(i+1 < sz(t))
            stream << ' ';
    }
    return stream;
}
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define _IWI(type,name,...) type name(__VA_ARGS__); cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
const int N = 1e5+5;
int depth[N];
vi adj[N];
void dfs(int u, int p){
    for(int v : adj[u])
        if(v != p){
            depth[v] = depth[u]+1;
            dfs(v,u);
        }
}
void __(){
    _(int,n);
    _(vpii,edges,n-1);
    if(n == 2){
        print 1,2;
        return;
    }
    vi deg(n+1);
    for(auto _ : edges)
        ++deg[_.X],++deg[_.Y];
    vpii nle;
    for(auto _ : edges){
        int u,v;
        tie(u,v) = _;
        if(deg[u] > 1 && deg[v] > 1)
            nle.pb({u,v});
        adj[u].pb(v);
        adj[v].pb(u);

    }
    map<int,int> cnt;
    for(auto _ : nle){
        cnt[_.X]++;
        cnt[_.Y]++;
    }
    vi ends;
    for(auto _ : cnt)
        if(_.Y == 1)
            ends.pb(_.X);
    if(sz(ends) > 2){
        print -1;
        return;
    }
    int root = 1;
    while(deg[root] == 1)
        ++root;
    if(!ends.empty())
        root = ends[0];
    dfs(root,-1);
    vpii sorted;
    rep(i,1,n)
        if(deg[i] > 1)
            sorted.pb({depth[i],i});
    sort(all(sorted));
    vi arr;
    for(auto _ : sorted){
        int u = _.Y;
        int cur = 0;
        for(int v : adj[u])
            if(deg[v] == 1)
                ++cur;
        arr.pb(cur);
    }
    assert(arr[0] > 0);
    arr.insert(arr.begin(),0);
    arr[1]--;
    assert(arr.back() > 0);
    arr.back()--;
    arr.pb(0);
    {
        vi test = arr;
        reverse(all(test));
        if(test < arr)
            arr = test;
    }
    vi ans;
    int nxt = 1;
    for(int x : arr){
        rep(i,x)
            ans.pb(nxt+1+i);
        ans.pb(nxt);
        nxt += x+1;
    }
    print ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}

Submission Info

Judge Result