//Time:1508ms //Memory:0KB //Length:1496B #include <iostream> #include <cstdio> #include <cstdlib> #include <queue> #include <cstring> using namespace std; #define MAXN 710 #define MAXM 60010 #define MOD 1000000007 #define INF 1000000007 int he[MAXN],to[MAXM],nex[MAXM],top; int fa[MAXN],len[MAXN],ans; bool vi[MAXN]; void add(int u,int v) { to[top]=v; nex[top]=he[u]; he[u]=top++; } int bfs(int s) { memset(vi,0,sizeof(vi)); queue<int> que; vi[s]=1,len[s]=0; fa[s]=-1; que.push(s); while(que.size()) { s=que.front(); que.pop(); if(len[s]*2-1>ans) break; for(int i=he[s];i!=-1;i=nex[i]) if(!vi[to[i]]) { vi[to[i]]=1; len[to[i]]=len[s]+1; fa[to[i]]=s; que.push(to[i]); } else if(to[i]!=fa[s]) ans=min(ans, len[s]+len[to[i]]+1); } return INF; } int main() { //freopen("/home/moor/Code/input","r",stdin); int ncase,n,m; scanf("%d",&ncase); for(int hh=1;hh<=ncase;++hh) { memset(he,-1,sizeof(he)); top=0; scanf("%d%d",&n,&m); for(int i=0;i<m;++i) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } ans=INF; for(int i=0;i<n&&ans>3;++i) bfs(i); printf("Case %d: ",hh); if(ans==INF) printf("impossible\n"); else printf("%d\n",ans); } return 0; } |
Double click to view unformatted code.