#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <queue>
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define compact(v) v.erase(unique(all(v)) , v.end())
#define pi pair<int , int>
#define vi vector<int>
#define eb emplace_back
#define FOR(i , l , r) for(int i = l; i <= r; ++ i)
#define FORD(i , l , r) for(int i = l; i >= r; -- i)
using namespace std;
typedef long long ll;
const int nd = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);
vi adj[nd];
vi leaf[nd];
queue <pi> ans;
void dfs(int r , int pre = 0){
//cout << r << '\n';
for(int v : adj[r]) if(v != pre){
dfs(v , r);
if(leaf[v].size() > leaf[r].size()) swap(leaf[v] , leaf[r]);
for(int node : leaf[v]) leaf[r].eb(node);
}
if(adj[r].size() == 1) leaf[r].eb(r);
//cout << r << " " << leaf[r].size() << '\n';
while(leaf[r].size() > 1){
int last = leaf[r].size() - 1;
ans.push({leaf[r][last] , leaf[r][last - 1]});
leaf[r].pop_back();
leaf[r].pop_back();
}
}
void solve(){
int n; cin >> n;
FOR(i , 2 , n){
int l , r;
cin >> l >> r;
adj[l].eb(r) , adj[r].eb(l);
}
if(n == 2){
cout << 1 << " " << 2;
return;
}
FOR(i , 1 , n) if(adj[i].size() > 1){
dfs(i);
if(leaf[i].size() != 0) ans.push({leaf[i][0] , i});
break;
}
cout << ans.size() << '\n';
while(ans.size()){
cout << ans.front().fi << " " << ans.front().se << '\n';
ans.pop();
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#define task "panh"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
solve();
return 0;
}
/*
-. ::. -: .::::::::::
***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
**##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######:
#%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####:
#####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####:
##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###:
%##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
*####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
#**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#:
####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##:
###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##:
###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########.
##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%%#:
#@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@ @#*+@*=##***##+*@###########:
@*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########:
@@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%%##########:
#@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########:
@%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########:
=: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######:
: :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######:
@@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%%:
##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####:
###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##.
#*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%%%#####.
**@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########.
++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########:
-@@@ @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########:
%@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%%#=#*%###########:
%@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########.
@@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########.
@@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%###########
:%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######.
:#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############.
++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@ @@.=@@@=*##*=@######%######
#%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%######
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%##########
+-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@#####
**%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%%#@###%+#=.@%########+%#####
#@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@ :@@%%@####@**-:@%######%*#*######
@%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%#################
=%#######+@@##@#+*=@##%%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*######
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*######
.#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%#####
:#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%#####
@@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*####
#####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####**
####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##********
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###**
#####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+***
.####**%%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#*************
####*#%*#####+#@@ =@%%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#***********
.#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++
######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#****
#####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++
####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+
##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@*
.##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@
#+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . #
*#****##%% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - .......
**++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:.
++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= .........
+######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:...
##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ......
####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...::::
*/
Compilation message (stderr)
net.cpp: In function 'int main()':
net.cpp:87:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
net.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |