#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; int n; vector g[100010]; int mn[100010]; bool dp[100010]; bool dp2[100010];//xの親側行って帰ってこれるか bool ep[100010], ep2[100010];//xの親側行けるか int par[100010]; void dfs(int x, int p){ dp[x]=1; par[x]=p; int mn=1e9, mx=-1; for(auto y:g[x]){ if(y==p) continue; mn=min(mn, y), mx=max(mx, y); dfs(y, x); if(!dp[y] || g[y][0]!=x){ dp[x]=0; } } if(mx==-1){ ep[x]=1; return; } bool ok1=ep[mx]; for(auto y:g[x]){ if(y==p) continue; if(mx!=y && (!dp[y] || g[y][0]!=x)){ ok1=0; } } bool ok2=ep[mn]; if(mn>par[x]) ok2=0; for(auto y:g[x]){ if(y==p) continue; if(mn!=y && (!dp[y] || g[y][0]!=x)){ ok2=0; } } if(ok1 || ok2) ep[x]=1; } void dfs2(int x, int p){ int y0=g[x][0]; int cnt=0; for(auto y:g[x]){ if(y==p){ if(dp2[x]) cnt++; }else if(y!=y0){ if(dp[y] && g[y][0]==x) cnt++; } } if(y0!=p && cnt==(int)g[x].size()-1){ dp2[y0]=1; } set st; for(auto y:g[x]) st.insert(y); cnt=0; for(auto y:g[x]){ if(y==p){ if(dp2[x]) cnt++; }else{ if(dp[y] && g[y][0]==x) cnt++; } } for(auto y:g[x]){ if(y==p) continue; int cnt1=0, cnt2=0; if(y==p){ if(dp2[x]) cnt1++; }else{ if(dp[y] && g[y][0]==x) cnt1++; } st.erase(y); int mx=*st.rbegin(); if(mx==p){ if(dp2[x]) cnt2++; }else{ if(dp[mx] && g[mx][0]==x) cnt2++; } bool e=0; if(mx==par[x]) e=ep2[x]; else e=ep[mx]; if(cnt-cnt1-cnt2==(int)g[x].size()-2 && e){ ep2[y]=1; } int mn=*st.begin(); cnt2=0; if(mn==p){ if(dp2[x]) cnt2++; }else{ if(dp[mn] && g[mn][0]==x) cnt2++; } e=0; if(mn==par[x]) e=ep2[x]; else e=ep[mn]; if(mn>n; for(int i=0; i>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } int r=0; for(int i=0; i1) r=i; } dfs(r, -1); dfs2(r, -1); for(int x=0; x