学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=3332

loriex:

唉这种题我都碰到不下5道了。。。

路径最小值最大 最大值最小什么的。。。

毫无新意

被虐哭了。。。。。一个小小的错误找了一天！！！！！！！！！！！！！！！！！！！！

感谢wulala以及loriex

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int T,n,m;
int fa[1005];
int f[1005][1005];
int id[1005];
int s[1005][1005];
int map[1005][1005];
int cnt;
struct data{int u,v;data(int u=0,int v=0):u(u),v(v){}};
vector<data>a[32768];

struct edge{int v,next;}e[2010];
int head[1010],k;

int s1[1010],s2[1010];
/////////////////////////////////////////////////
void adde(int u,int v){e[k].v=v;e[k].next=head[u];head[u]=k++;}
void dfs(int u,int *s,int fa)
{
	s[++*s]=u;
	INE(i,u,e)
	{
		int v=e[i].v; if(v==fa) continue;
		dfs(v,s,u);
	}
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline bool unio(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy) return 0;
	fa[fx]=fy;
	return 1;
}
inline void No()
{
	printf("Case #%d: No\n",T);
}
/////////////////////////////////////////////////
void input()
{
	MS(id,0); cnt=0; MS(head,-1); k=0;// MS(s,0);
	rep(i,1,1000) *s[i]=0;
	
    n=read(); m=read();
    rep(i,1,n) fa[i]=i;
    rep(i,1,m)
    {
    	int u=read(),v=read();
    	unio(u,v);
    	map[u][v]=map[v][u]=T;
    }
    rep(i,1,n) rep(j,1,n) f[i][j]=read();
}
void solve()
{
	bool flag=1;
	rep(i,1,n) rep(j,1,i-1)
	{
		if(f[i][j]==-1)
		{
			if(find(i)==find(j)){No();return;}
		}
		if(f[i][j]!=f[j][i]){No();return;}
		if(f[i][i]!=0){No();return;}
	}
	//printf("%d\n",cmp);
	rep(i,1,n)
	{
		int rt=find(i);
		if(!id[rt]) id[rt]=++cnt;
		int &top=*s[id[rt]];
		s[id[rt]][++top]=i;
	}
	rep(i,1,cnt)
	{
		rep(j,1,32767) a[j].clear();
		rep(x,1,*s[i]) rep(y,1,x-1)
		{
			int u=s[i][x],v=s[i][y];
			int w=f[u][v];
			if(map[u][v]==T) a[w].push_back(data(u,v));
		}
		rep(j,1,*s[i]) fa[s[i][j]]=s[i][j];
		int block=*s[i];
		per(j,32767,1)
		{
			rep(k,0,a[j].size()-1)
			{
				int u=a[j][k].u,v=a[j][k].v;
				if(unio(u,v))
				{
					block--;
					*s1=0; dfs(u,s1,-1);
					*s2=0; dfs(v,s2,-1);
					rep(i,1,*s1) rep(j,1,*s2) if(f[s1[i]][s2[j]]!=f[u][v]){No();return;}
					adde(u,v); adde(v,u);
				}
				else if(f[u][v]<j) {No();return;}
				if(block==1) break;
			}
			if(block==1) break;
		}
	}
	printf("Case #%d: Yes\n",T);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("wl2.out","w",stdout);
    #endif
    int t=read();
    for(T=1;T<=t;T++)
    input(),solve();
    return 0;
}