#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, m; int a[200020]; vector g[200020]; int dp[200020]; void dfs(int x, int p){ set st; for(auto y:g[x]){ if(y==p) continue; dfs(y, x); st.insert(dp[y]); } for(int i=0; ; i++){ if(st.find(i)==st.end()){ dp[x]=i; break; } } } int dp2[200020]; int gr[200020]; int par[200020]; void dfs2(int x, int p){ par[x]=p; map mp; for(auto y:g[x]){ if(y==p) mp[dp2[x]]++; else mp[dp[y]]++; } int mn; for(int i=0; ; i++){ if(mp.find(i)==mp.end()){ mn=i; break; } } gr[x]=mn; for(auto y:g[x]){ if(y==p) continue; if(dp[y]>mn || mp[dp[y]]>1){ dp2[y]=mn; }else{ dp2[y]=dp[y]; } } for(auto y:g[x]){ if(y==p) continue; dfs2(y, x); } } int b[200020]; int main() { cin>>n>>m; for(int i=0; i>a[i]; a[i]--; b[a[i]]=i+1; } for(int i=0; i>u>>v; u--; v--; g[u].push_back(v); g[v].push_back(u); } dfs(0, -1); dfs2(0, -1); int s=0; for(int i=0; i