#include <bits/stdc++.h>
#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//
//#define int long long
////#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
vector<vector<int> > g;
vector<int> pr;
vector<int> tin, tout;
vector<int> ls;
vector<int> ord;
vector<int> tin_ord;
int timer = 0;
void dfs(int v, int p)
{
tin[v] = timer++;
pr[v] = p;
if (g[v].size() == 1){
ls[v]++;
tin_ord.push_back(tin[v]);
ord.push_back(v);
}
for (auto&u : g[v])
{
if (u != p)
{
dfs(u, v);
ls[v] += ls[u];
}
}
tout[v] = timer++;
}
int root = 0;
int cock(int v, int p)
{
for (auto& u : g[v])
{
if (u != p)
{
if (ls[u] > ls[root] / 2)
{
return cock(u, v);
}
}
}
return v;
}
void solve()
{
int n;
cin >> n;
g.resize(n);
pr.resize(n);
ls.resize(n);
tin.resize(n);
tout.resize(n);
for (int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i < n; i++)
if (g[i].size() > 1)
root = i;
dfs(root, root);
vector<int> ans(ls[root] + ls[root] % 2);
vector<int> cur;
int j = cock(root, root);
int lt = lower_bound(tin_ord.begin(), tin_ord.end(), tin[j]) - tin_ord.begin();
int rt = upper_bound(tin_ord.begin(), tin_ord.end(), tout[j]) - tin_ord.begin() - 1;
int k = 0;
for (int i = 0; i < lt; i++)
{
ans[k] = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
for (int i = rt + 1; i < ord.size(); i++)
{
ans[k] = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
for (auto& u : g[j])
{
if (u != pr[j])
{
int l = lower_bound(tin_ord.begin(), tin_ord.end(), tin[u]) - tin_ord.begin();
int r = upper_bound(tin_ord.begin(), tin_ord.end(), tout[u]) - tin_ord.begin() - 1;
for (int i = l; i <= r; i++)
{
ans[k] = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
}
}
if (ls[root] % 2 == 1)
{
ans[ans.size() - 1] = 1;
}
cout << ans.size() / 2 << endl;
for (int i = 0; i < ans.size(); i += 2)
{
cout << ans[i] + 1 << ' ' << ans[i + 1] + 1 << endl;
}
}
//
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
//cin >> t;
while (t--)
{
solve();
}
cerr << endl << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
return 0;
}
//
//
/*
17 13
1 3 1 2 1 3 1 2 1 1 2 1 2 1 2 1 3
3 1 2 3 3 2 1 2 1 3 2 2 1
*/
/*
6 9
3 2 1 6 7 4
3 2 6 10 8 9 7 1 4
*/
/*
9 8
2 1 4 6 7 8 9 10 11
8 9 10 11 1 4 6 7
*/
Compilation message
net.cpp: In function 'void solve()':
net.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = rt + 1; i < ord.size(); i++)
| ~~^~~~~~~~~~~~
net.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int i = 0; i < ans.size(); i += 2)
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 8 |
Halted |
0 ms |
0 KB |
- |
