/*思前想后  还是决定坚持写博客吧...题意：n个点，m个集合。每个集合里边的点是联通的且任意两点之间有一条dis[i]的边（每个集合一个dis[i]）求同时从第1个点和第n个点出发的两个人相遇的最短时间，并输出相遇的地点，如果有多个按编号大小顺序输出。输入：测试数据 tn m 以下m行每行dis[i] 该集合点的数量 ...每个点的标号数据范围：n 2-1e5所有集合的元素的数量和 1e6思路：如果直接跑最短路，边会存爆的。考虑换种思路建边。每个集合看作两个点，一个为入点一个为出点，从出点往入点连接一条dis[i]的边。然后再从入点往集合里包含的点连一条权值为0的边，从该点网出点连一条权值为0的边。这样建图 大概有2e6个点  3e6条边...然后利用heap优化dij就可以解决从1到其它所有点的最短路，和从n到其它所有点的最短路。然后扫描一下...反思：1.PE这种事最可耻了2.我想到了每个集合多加两个点，但是后边就有点崩了。图论还需多看。3.这题不难不难不难。多用心。多想想。*/#include<bits/stdc++.h>#define N 2500000#define M 3500000using namespace std;struct st{    int id;    long long dis;    st(int a,long long b)    {        id=a;        dis=b;    }    st(){};};bool operator < (const st &a,const st &b){    return a.dis>b.dis;}struct edge{    int id;    long long w;    edge *next;};int ednum;edge edges[M];edge *adj[N];long long dis1[N],dis2[N];long long inf=0x3f3f3f3f3f3f3f3f;inline void addedge(int a,int b,long long dis){    edge *tmp=&edges[ednum++];    tmp->id=b;    tmp->next=adj[a];    tmp->w=dis;    adj[a]=tmp;}void heap_dij(int tar,int MAXN,long long *dis){    for(int i=1;i<=MAXN;i++){        dis[i]=inf;    }    priority_queue<st>q;    st tmp;    dis[tar]=0;    q.push(st(tar,0));    while(!q.empty())    {        tmp=q.top();        q.pop();        if(dis[tmp.id]<tmp.dis)continue;        for(edge *p=adj[tmp.id];p;p=p->next)        {            if(dis[p->id]>p->w+dis[tmp.id])            {               dis[p->id]=p->w+dis[tmp.id];               q.push(st(p->id,dis[p->id]));            }        }    }}int main(){    int t,cas=0;    scanf("%d",&t);    while(t--){        ednum=0;        memset(adj,NULL,sizeof(adj));        cas++;        int n,m;        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++){            long long d;            int nn;            scanf("%lld%d",&d,&nn);            addedge(n+2*(i-1)+2,n+2*(i-1)+1,d);            for(int j=1;j<=nn;j++){                int tmp;                scanf("%d",&tmp);                addedge(n+2*(i-1)+1,tmp,0);                addedge(tmp,n+2*(i-1)+2,0);            }        }        heap_dij(1,2*m+n,dis1);        heap_dij(n,2*m+n,dis2);        long long ans=inf;        printf("Case #%d: ",cas);        for(int i=1;i<=n;i++){            ans=min(ans,max(dis1[i],dis2[i]));        }        if(ans==inf)puts("Evil John");        else printf("%lld\n",ans);        bool ok=0;        if(ans!=inf)        for(int i=1;i<=n;i++){            if(max(dis1[i],dis2[i])==ans){                if(ok)printf(" %d",i);                else{                    ok=1;                    printf("%d",i);                }            }        }        if(ans!=inf)puts("");    }}