Advertisement
amine99

Untitled

May 27th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define ALL(x) x.begin(),x.end()
  5. #define SZ(x) x.size()
  6. #define PB push_back
  7. #define MP make_pair
  8. #define F first
  9. #define S second
  10. typedef long long LL;
  11. typedef vector<int> VI;
  12. typedef pair<int,int> PI;
  13.  
  14. const int N=1e5+1;
  15. vector<VI> g;
  16. int n,h,d[N],f,x;
  17. VI ans;
  18. bool vis[N];
  19.  
  20. void dfs(int u,int v) {
  21.    if(!f)
  22.       return;
  23.    if(v && SZ(g[u]) > 2) {
  24.       f = 0;
  25.       return;
  26.    }
  27.    vis[u] = true;
  28.    for(int i = 0; i < SZ(g[u]); i++) {
  29.       if(!vis[g[u][i]])
  30.          dfs(g[u][i],1);
  31.    }
  32. }
  33.  
  34. void solve(int u) {
  35.    vis[u] = 1;
  36.    if(SZ(g[u]) == 1 && u != x)
  37.       ans.PB(u);
  38.    for(int i = 0; i < SZ(g[u]); i++) {
  39.       if(!vis[g[u][i]])
  40.          solve(g[u][i]);
  41.    }
  42. }
  43.  
  44. int main() {
  45.    io
  46.    cin >> n;
  47.    g.clear();
  48.    g.resize(n+1);
  49.    h = 1;
  50.    for(int i = 0; i < n-1; i++) {
  51.       int u,v;
  52.       cin >> u >> v;
  53.       g[u].PB(v); d[u]++;
  54.       g[v].PB(u); d[v]++;
  55.       if(d[u] > d[h])
  56.          h = u;
  57.       if(d[v] > d[h])
  58.          h = v;
  59.    }
  60.    f = 1;
  61.    x = -1;
  62.    dfs(h,0);
  63.    if(f)
  64.       x = h;
  65.    if(x == -1)
  66.       return 0*puts("No");
  67.    memset(vis,0,sizeof(vis));
  68.    solve(x);
  69.    puts("Yes");
  70.    cout << SZ(ans) << "\n";
  71.    for(int i = 0; i < SZ(ans); i++)
  72.       cout << x << " " << ans[i] << "\n";
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement