/*
_________ .---""" """---.
:______.-': : .--------------. :
| ______ | | : : |
|:______B:| | | Little Error: | |
|:______B:| | | | |
|:______B:| | | Power not | |
| | | | found. | |
|:_____: | | | | |
| == | | : : |
| O | : '--------------' :
| o | :'---...______...---'
| o |-._.-i___/' \._
|'-.____o_| '-. '-...______...-' `-._
:_________: `.____________________ `-.___.-.
.'.eeeeeeeeeeeeeeeeee.'. :___:
fsc .'.eeeeeeeeeeeeeeeeeeeeee.'.
:____________________________:
*/
//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define endl "\n"
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
const int maxn=5e5+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;
ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));}
int n ;
int deg ;
int DD[maxn];
vector<int> B ;
vector<int> adj[maxn];
int cnt ;
void dfs(int v, int P = 0){
DD[v] = deg++;
for(auto u : adj[v]){
if(u == P){
continue;
}
dfs(u, v);
}
}
bool cmp(int i, int j){
return DD[i] < DD[j];
}
int main(){
cin >> n ;
int root =1 ;
for(int i = 1; i < n ;i ++){
int x ;
int y ;
cin >> x >> y ;
adj[x].push_back(y) ;
adj[y].push_back(x) ;
}
for(int i = 1; i <= n; i ++){
if(adj[i].size() > 1){
root = i;
}
if(adj[i].size() == 1){
B.pb(i);
cnt++;
}
}
dfs(root);
sort(B.begin() , B.end() , cmp);
cout<<(cnt + 1 ) / 2 <<endl ;
cnt = (cnt + 1) / 2 ;
for(int i = 0 ; i + cnt < B.size() ; i ++ ){
cout<<B[i] <<" " << B[i + cnt] << endl ;
}
if(B.size() % 2 == 1){
cout<<B[cnt-1] <<" " << B[0] << endl ;
}
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i = 0 ; i + cnt < B.size() ; i ++ ){
| ~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11980 KB |
Output is correct |
2 |
Correct |
9 ms |
11980 KB |
Output is correct |
3 |
Correct |
8 ms |
11980 KB |
Output is correct |
4 |
Correct |
8 ms |
11980 KB |
Output is correct |
5 |
Correct |
8 ms |
11980 KB |
Output is correct |
6 |
Correct |
8 ms |
11980 KB |
Output is correct |
7 |
Correct |
8 ms |
11980 KB |
Output is correct |
8 |
Correct |
8 ms |
11980 KB |
Output is correct |
9 |
Correct |
8 ms |
11984 KB |
Output is correct |
10 |
Correct |
8 ms |
11976 KB |
Output is correct |
11 |
Correct |
9 ms |
11980 KB |
Output is correct |
12 |
Correct |
8 ms |
11980 KB |
Output is correct |
13 |
Correct |
8 ms |
11980 KB |
Output is correct |
14 |
Correct |
9 ms |
11980 KB |
Output is correct |
15 |
Correct |
9 ms |
11980 KB |
Output is correct |
16 |
Correct |
8 ms |
12052 KB |
Output is correct |
17 |
Correct |
8 ms |
11996 KB |
Output is correct |
18 |
Correct |
8 ms |
11980 KB |
Output is correct |
19 |
Correct |
8 ms |
11956 KB |
Output is correct |
20 |
Correct |
8 ms |
11980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11980 KB |
Output is correct |
2 |
Correct |
9 ms |
11980 KB |
Output is correct |
3 |
Correct |
8 ms |
11980 KB |
Output is correct |
4 |
Correct |
8 ms |
11980 KB |
Output is correct |
5 |
Correct |
8 ms |
11980 KB |
Output is correct |
6 |
Correct |
8 ms |
11980 KB |
Output is correct |
7 |
Correct |
8 ms |
11980 KB |
Output is correct |
8 |
Correct |
8 ms |
11980 KB |
Output is correct |
9 |
Correct |
8 ms |
11984 KB |
Output is correct |
10 |
Correct |
8 ms |
11976 KB |
Output is correct |
11 |
Correct |
9 ms |
11980 KB |
Output is correct |
12 |
Correct |
8 ms |
11980 KB |
Output is correct |
13 |
Correct |
8 ms |
11980 KB |
Output is correct |
14 |
Correct |
9 ms |
11980 KB |
Output is correct |
15 |
Correct |
9 ms |
11980 KB |
Output is correct |
16 |
Correct |
8 ms |
12052 KB |
Output is correct |
17 |
Correct |
8 ms |
11996 KB |
Output is correct |
18 |
Correct |
8 ms |
11980 KB |
Output is correct |
19 |
Correct |
8 ms |
11956 KB |
Output is correct |
20 |
Correct |
8 ms |
11980 KB |
Output is correct |
21 |
Correct |
8 ms |
11980 KB |
Output is correct |
22 |
Correct |
10 ms |
12108 KB |
Output is correct |
23 |
Correct |
10 ms |
12108 KB |
Output is correct |
24 |
Correct |
10 ms |
12140 KB |
Output is correct |
25 |
Correct |
9 ms |
12108 KB |
Output is correct |
26 |
Correct |
9 ms |
12048 KB |
Output is correct |
27 |
Correct |
9 ms |
12108 KB |
Output is correct |
28 |
Correct |
10 ms |
12108 KB |
Output is correct |
29 |
Correct |
9 ms |
12108 KB |
Output is correct |
30 |
Correct |
8 ms |
11960 KB |
Output is correct |
31 |
Correct |
9 ms |
12048 KB |
Output is correct |
32 |
Correct |
9 ms |
11980 KB |
Output is correct |
33 |
Correct |
8 ms |
11980 KB |
Output is correct |
34 |
Correct |
8 ms |
11980 KB |
Output is correct |
35 |
Correct |
8 ms |
11980 KB |
Output is correct |
36 |
Correct |
8 ms |
11980 KB |
Output is correct |
37 |
Correct |
8 ms |
11980 KB |
Output is correct |
38 |
Correct |
8 ms |
12112 KB |
Output is correct |
39 |
Correct |
8 ms |
11980 KB |
Output is correct |
40 |
Correct |
9 ms |
12024 KB |
Output is correct |
41 |
Correct |
8 ms |
11980 KB |
Output is correct |
42 |
Correct |
8 ms |
11980 KB |
Output is correct |
43 |
Correct |
8 ms |
12048 KB |
Output is correct |
44 |
Correct |
8 ms |
11932 KB |
Output is correct |
45 |
Correct |
8 ms |
11980 KB |
Output is correct |
46 |
Correct |
9 ms |
11980 KB |
Output is correct |
47 |
Correct |
8 ms |
11984 KB |
Output is correct |
48 |
Correct |
9 ms |
11980 KB |
Output is correct |
49 |
Correct |
9 ms |
12100 KB |
Output is correct |
50 |
Correct |
8 ms |
11980 KB |
Output is correct |
51 |
Correct |
8 ms |
11948 KB |
Output is correct |
52 |
Correct |
8 ms |
11984 KB |
Output is correct |
53 |
Correct |
9 ms |
11980 KB |
Output is correct |
54 |
Correct |
8 ms |
12044 KB |
Output is correct |
55 |
Correct |
8 ms |
11980 KB |
Output is correct |
56 |
Correct |
8 ms |
11980 KB |
Output is correct |
57 |
Correct |
9 ms |
11980 KB |
Output is correct |
58 |
Correct |
10 ms |
12108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11980 KB |
Output is correct |
2 |
Correct |
9 ms |
11980 KB |
Output is correct |
3 |
Correct |
8 ms |
11980 KB |
Output is correct |
4 |
Correct |
8 ms |
11980 KB |
Output is correct |
5 |
Correct |
8 ms |
11980 KB |
Output is correct |
6 |
Correct |
8 ms |
11980 KB |
Output is correct |
7 |
Correct |
8 ms |
11980 KB |
Output is correct |
8 |
Correct |
8 ms |
11980 KB |
Output is correct |
9 |
Correct |
8 ms |
11984 KB |
Output is correct |
10 |
Correct |
8 ms |
11976 KB |
Output is correct |
11 |
Correct |
9 ms |
11980 KB |
Output is correct |
12 |
Correct |
8 ms |
11980 KB |
Output is correct |
13 |
Correct |
8 ms |
11980 KB |
Output is correct |
14 |
Correct |
9 ms |
11980 KB |
Output is correct |
15 |
Correct |
9 ms |
11980 KB |
Output is correct |
16 |
Correct |
8 ms |
12052 KB |
Output is correct |
17 |
Correct |
8 ms |
11996 KB |
Output is correct |
18 |
Correct |
8 ms |
11980 KB |
Output is correct |
19 |
Correct |
8 ms |
11956 KB |
Output is correct |
20 |
Correct |
8 ms |
11980 KB |
Output is correct |
21 |
Correct |
8 ms |
11980 KB |
Output is correct |
22 |
Correct |
10 ms |
12108 KB |
Output is correct |
23 |
Correct |
10 ms |
12108 KB |
Output is correct |
24 |
Correct |
10 ms |
12140 KB |
Output is correct |
25 |
Correct |
9 ms |
12108 KB |
Output is correct |
26 |
Correct |
9 ms |
12048 KB |
Output is correct |
27 |
Correct |
9 ms |
12108 KB |
Output is correct |
28 |
Correct |
10 ms |
12108 KB |
Output is correct |
29 |
Correct |
9 ms |
12108 KB |
Output is correct |
30 |
Correct |
8 ms |
11960 KB |
Output is correct |
31 |
Correct |
9 ms |
12048 KB |
Output is correct |
32 |
Correct |
9 ms |
11980 KB |
Output is correct |
33 |
Correct |
8 ms |
11980 KB |
Output is correct |
34 |
Correct |
8 ms |
11980 KB |
Output is correct |
35 |
Correct |
8 ms |
11980 KB |
Output is correct |
36 |
Correct |
8 ms |
11980 KB |
Output is correct |
37 |
Correct |
8 ms |
11980 KB |
Output is correct |
38 |
Correct |
8 ms |
12112 KB |
Output is correct |
39 |
Correct |
8 ms |
11980 KB |
Output is correct |
40 |
Correct |
9 ms |
12024 KB |
Output is correct |
41 |
Correct |
8 ms |
11980 KB |
Output is correct |
42 |
Correct |
8 ms |
11980 KB |
Output is correct |
43 |
Correct |
8 ms |
12048 KB |
Output is correct |
44 |
Correct |
8 ms |
11932 KB |
Output is correct |
45 |
Correct |
8 ms |
11980 KB |
Output is correct |
46 |
Correct |
9 ms |
11980 KB |
Output is correct |
47 |
Correct |
8 ms |
11984 KB |
Output is correct |
48 |
Correct |
9 ms |
11980 KB |
Output is correct |
49 |
Correct |
9 ms |
12100 KB |
Output is correct |
50 |
Correct |
8 ms |
11980 KB |
Output is correct |
51 |
Correct |
8 ms |
11948 KB |
Output is correct |
52 |
Correct |
8 ms |
11984 KB |
Output is correct |
53 |
Correct |
9 ms |
11980 KB |
Output is correct |
54 |
Correct |
8 ms |
12044 KB |
Output is correct |
55 |
Correct |
8 ms |
11980 KB |
Output is correct |
56 |
Correct |
8 ms |
11980 KB |
Output is correct |
57 |
Correct |
9 ms |
11980 KB |
Output is correct |
58 |
Correct |
10 ms |
12108 KB |
Output is correct |
59 |
Correct |
631 ms |
31756 KB |
Output is correct |
60 |
Correct |
739 ms |
34012 KB |
Output is correct |
61 |
Correct |
8 ms |
11984 KB |
Output is correct |
62 |
Correct |
8 ms |
11980 KB |
Output is correct |
63 |
Correct |
554 ms |
29744 KB |
Output is correct |
64 |
Correct |
12 ms |
12364 KB |
Output is correct |
65 |
Correct |
27 ms |
13508 KB |
Output is correct |
66 |
Correct |
219 ms |
23596 KB |
Output is correct |
67 |
Correct |
786 ms |
53100 KB |
Output is correct |
68 |
Correct |
769 ms |
45824 KB |
Output is correct |
69 |
Correct |
22 ms |
12748 KB |
Output is correct |
70 |
Correct |
186 ms |
19812 KB |
Output is correct |
71 |
Correct |
656 ms |
37060 KB |
Output is correct |
72 |
Correct |
644 ms |
36244 KB |
Output is correct |
73 |
Correct |
168 ms |
17848 KB |
Output is correct |
74 |
Correct |
769 ms |
33032 KB |
Output is correct |
75 |
Correct |
65 ms |
14820 KB |
Output is correct |
76 |
Correct |
642 ms |
36752 KB |
Output is correct |
77 |
Correct |
630 ms |
37136 KB |
Output is correct |
78 |
Correct |
72 ms |
15020 KB |
Output is correct |
79 |
Correct |
716 ms |
40420 KB |
Output is correct |
80 |
Correct |
11 ms |
12236 KB |
Output is correct |
81 |
Correct |
218 ms |
19848 KB |
Output is correct |
82 |
Correct |
743 ms |
35040 KB |
Output is correct |
83 |
Correct |
725 ms |
32952 KB |
Output is correct |
84 |
Correct |
739 ms |
33044 KB |
Output is correct |
85 |
Correct |
727 ms |
33080 KB |
Output is correct |
86 |
Correct |
745 ms |
34048 KB |
Output is correct |
87 |
Correct |
756 ms |
33984 KB |
Output is correct |