[HOJ] 180 - 蟲蟲集結

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> s[50005];
int is[50005]={0},v[50005]={0},c[50005],L=0,id,tmp=1,pp=-1;
void dfs(int u,int add){
    c[add]=u;
    if(is[u]==1){
        pp++;
        if(add%2!=L/2%2) tmp=0;
        if(add>L) L=add,id=u;
    }
    for(int i=0;i<s[u].size();i++){
        int p=s[u][i];
        if(v[p]==0){
            v[p]=1;
            dfs(p,add+1);
        }
    }
}
int main(){
    int n,m,i,j,k,p,x,y;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
    }
    scanf("%d",&k);
    for(i=0;i<k;i++){
        scanf("%d",&x);
        is[x]=1;
    }
    v[x]=1;
    dfs(x,0);
    memset(v,0,sizeof(v));
    v[id]=1;
    dfs(id,0);
    memset(v,0,sizeof(v));
    tmp=1,id=c[L/2],pp=0;
    v[id]=1;
    dfs(id,0);
    if(L%2 || !tmp || pp!=k) puts("NIE");
    else printf("%d\n",L/2);
}