Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define ALL(x) x.begin(),x.end()
- #define SZ(x) x.size()
- #define PB push_back
- #define MP make_pair
- #define F first
- #define S second
- typedef long long LL;
- typedef vector<int> VI;
- typedef pair<int,int> PI;
- const int N=1e5+1;
- vector<VI> g;
- int n,h,d[N],f,x;
- VI ans;
- bool vis[N];
- void dfs(int u,int v) {
- if(!f)
- return;
- if(v && SZ(g[u]) > 2) {
- f = 0;
- return;
- }
- vis[u] = true;
- for(int i = 0; i < SZ(g[u]); i++) {
- if(!vis[g[u][i]])
- dfs(g[u][i],1);
- }
- }
- void solve(int u) {
- vis[u] = 1;
- if(SZ(g[u]) == 1 && u != x)
- ans.PB(u);
- for(int i = 0; i < SZ(g[u]); i++) {
- if(!vis[g[u][i]])
- solve(g[u][i]);
- }
- }
- int main() {
- io
- cin >> n;
- g.clear();
- g.resize(n+1);
- h = 1;
- for(int i = 0; i < n-1; i++) {
- int u,v;
- cin >> u >> v;
- g[u].PB(v); d[u]++;
- g[v].PB(u); d[v]++;
- if(d[u] > d[h])
- h = u;
- if(d[v] > d[h])
- h = v;
- }
- f = 1;
- x = -1;
- dfs(h,0);
- if(f)
- x = h;
- if(x == -1)
- return 0*puts("No");
- memset(vis,0,sizeof(vis));
- solve(x);
- puts("Yes");
- cout << SZ(ans) << "\n";
- for(int i = 0; i < SZ(ans); i++)
- cout << x << " " << ans[i] << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement