#include <bits/stdc++.h>
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
#define int long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=5e5+5,M=1e3+1,Mod=1e9+7;
vector<int>adj[N],par[N];
int n,dep[N];
void testcase(int h){
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
dep[u]++;
dep[v]++;
}
deque<pair<int,int>>ans;
vector<pair<int,int>>leaf;
for(int i=1;i<=n;i++){
if(dep[i]==1){
leaf.push_back({adj[i][0],i});
}
}
sort(all(leaf));
int sz=leaf.size();
if(sz%2){
cout<<sz/2+1<<el;
for(int i=0;i<sz/2;i++){
cout<<leaf[i].S<<' '<<leaf[i+sz/2+1].S<<el;
}
cout<<leaf[sz/2].S<<' '<<1<<el;
}
else{
cout<<sz/2<<el;
for(int i=0;i<sz/2;i++){
cout<<leaf[i].S<<' '<<leaf[i+sz/2].S<<el;
}
}
}
int32_t main()
{
// fast
testcase(1);
// int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23700 KB |
Output is correct |
3 |
Correct |
12 ms |
23724 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23708 KB |
Output is correct |
7 |
Correct |
12 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23892 KB |
Output is correct |
9 |
Correct |
15 ms |
23764 KB |
Output is correct |
10 |
Correct |
16 ms |
23776 KB |
Output is correct |
11 |
Correct |
13 ms |
23792 KB |
Output is correct |
12 |
Correct |
14 ms |
23744 KB |
Output is correct |
13 |
Correct |
13 ms |
23780 KB |
Output is correct |
14 |
Correct |
13 ms |
23764 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23792 KB |
Output is correct |
17 |
Correct |
12 ms |
23712 KB |
Output is correct |
18 |
Correct |
12 ms |
23792 KB |
Output is correct |
19 |
Correct |
12 ms |
23764 KB |
Output is correct |
20 |
Correct |
14 ms |
23764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23700 KB |
Output is correct |
3 |
Correct |
12 ms |
23724 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23708 KB |
Output is correct |
7 |
Correct |
12 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23892 KB |
Output is correct |
9 |
Correct |
15 ms |
23764 KB |
Output is correct |
10 |
Correct |
16 ms |
23776 KB |
Output is correct |
11 |
Correct |
13 ms |
23792 KB |
Output is correct |
12 |
Correct |
14 ms |
23744 KB |
Output is correct |
13 |
Correct |
13 ms |
23780 KB |
Output is correct |
14 |
Correct |
13 ms |
23764 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23792 KB |
Output is correct |
17 |
Correct |
12 ms |
23712 KB |
Output is correct |
18 |
Correct |
12 ms |
23792 KB |
Output is correct |
19 |
Correct |
12 ms |
23764 KB |
Output is correct |
20 |
Correct |
14 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23764 KB |
Output is correct |
22 |
Correct |
15 ms |
23928 KB |
Output is correct |
23 |
Correct |
15 ms |
23936 KB |
Output is correct |
24 |
Correct |
14 ms |
23892 KB |
Output is correct |
25 |
Correct |
14 ms |
23892 KB |
Output is correct |
26 |
Correct |
15 ms |
23892 KB |
Output is correct |
27 |
Correct |
13 ms |
23844 KB |
Output is correct |
28 |
Correct |
14 ms |
23892 KB |
Output is correct |
29 |
Correct |
12 ms |
23892 KB |
Output is correct |
30 |
Correct |
12 ms |
23764 KB |
Output is correct |
31 |
Correct |
14 ms |
23892 KB |
Output is correct |
32 |
Correct |
13 ms |
23712 KB |
Output is correct |
33 |
Correct |
13 ms |
23772 KB |
Output is correct |
34 |
Incorrect |
12 ms |
23764 KB |
Breaking single line is causing network to disconnect. |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23700 KB |
Output is correct |
3 |
Correct |
12 ms |
23724 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23708 KB |
Output is correct |
7 |
Correct |
12 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23892 KB |
Output is correct |
9 |
Correct |
15 ms |
23764 KB |
Output is correct |
10 |
Correct |
16 ms |
23776 KB |
Output is correct |
11 |
Correct |
13 ms |
23792 KB |
Output is correct |
12 |
Correct |
14 ms |
23744 KB |
Output is correct |
13 |
Correct |
13 ms |
23780 KB |
Output is correct |
14 |
Correct |
13 ms |
23764 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23792 KB |
Output is correct |
17 |
Correct |
12 ms |
23712 KB |
Output is correct |
18 |
Correct |
12 ms |
23792 KB |
Output is correct |
19 |
Correct |
12 ms |
23764 KB |
Output is correct |
20 |
Correct |
14 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23764 KB |
Output is correct |
22 |
Correct |
15 ms |
23928 KB |
Output is correct |
23 |
Correct |
15 ms |
23936 KB |
Output is correct |
24 |
Correct |
14 ms |
23892 KB |
Output is correct |
25 |
Correct |
14 ms |
23892 KB |
Output is correct |
26 |
Correct |
15 ms |
23892 KB |
Output is correct |
27 |
Correct |
13 ms |
23844 KB |
Output is correct |
28 |
Correct |
14 ms |
23892 KB |
Output is correct |
29 |
Correct |
12 ms |
23892 KB |
Output is correct |
30 |
Correct |
12 ms |
23764 KB |
Output is correct |
31 |
Correct |
14 ms |
23892 KB |
Output is correct |
32 |
Correct |
13 ms |
23712 KB |
Output is correct |
33 |
Correct |
13 ms |
23772 KB |
Output is correct |
34 |
Incorrect |
12 ms |
23764 KB |
Breaking single line is causing network to disconnect. |
35 |
Halted |
0 ms |
0 KB |
- |