import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def get_root(s):
v = []
while not s == root[s]:
v.append(s)
s = root[s]
for i in v:
root[i] = s
return s
def unite(s, t):
rs, rt = get_root(s), get_root(t)
if not rs ^ rt:
return
if rank[s] == rank[t]:
rank[rs] += 1
if rank[s] >= rank[t]:
root[rt] = rs
size[rs] += size[rt]
else:
root[rs] = rt
size[rt] += size[rs]
return
def same(s, t):
return True if get_root(s) == get_root(t) else False
def get_size(s):
return size[get_root(s)]
n = int(input())
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
l = [i for i in range(n + 1)]
r = [i for i in range(n + 1)]
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
x, y = map(int, input().split())
x0, y0 = get_root(x), get_root(y)
lx, ly = l[x0], l[y0]
rx, ry = r[x0], r[y0]
G[lx].append(ry)
G[ry].append(lx)
unite(x, y)
r0 = get_root(x)
l[r0], r[r0] = rx, ly
for i in range(1, n + 1):
if len(G[i]) == 1:
s = i
break
ans = [s, G[s][0]]
for _ in range(n - 2):
for i in G[ans[-1]]:
if i ^ ans[-2]:
ans.append(i)
break
sys.stdout.write(" ".join(map(str, ans)))#include <bits/stdc++.h>
using namespace std;
const int c=200005;
int n;
vector<pair<int, int> > sz[c];
bool v[c];
priority_queue<pair<int, int> > q;
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=1; i<n; i++) {
int a, b;
cin >> a >> b;
sz[a].push_back({b, i});
sz[b].push_back({a, i});
}
for (int i=2; i<=n; i++) {
sz[1].push_back({i, n});
}
q.push({0, 1});
while (q.size()>0) {
int a=q.top().second;
q.pop();
if (v[a]) continue;
cout << a << " ";
v[a]=true;
for (auto p:sz[a]) {
int b=p.first, x=p.second;
if (!v[b]) {
q.push({-x, b});
}
}
}
cout << "\n";
return 0;
}1660C - Get an Even String | 489B - BerSU Ball |
977C - Less or Equal | 1505C - Fibonacci Words |
1660A - Vasya and Coins | 1660E - Matrix and Shifts |
1293B - JOE is on TV | 1584A - Mathematical Addition |
1660B - Vlad and Candies | 1472C - Long Jumps |
1293D - Aroma's Search | 918A - Eleven |
1237A - Balanced Rating Changes | 1616A - Integer Diversity |
1627B - Not Sitting | 1663C - Pōja Verdon |
1497A - Meximization | 1633B - Minority |
688B - Lovely Palindromes | 66B - Petya and Countryside |
1557B - Moamen and k-subarrays | 540A - Combination Lock |
1553C - Penalty | 1474E - What Is It |
1335B - Construct the String | 1004B - Sonya and Exhibition |
1397A - Juggling Letters | 985C - Liebig's Barrels |
115A - Party | 746B - Decoding |