遍历下界，二分上届。dfs是否合适。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 99999999
#define maxn 4001
struct list
{int u;int v;int next;int l;int r;
}node[maxn*4];
int head[maxn];
int vis[maxn];
int nums;
int n,m;
void init()
{memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));nums=0;
}
void add(int a,int b,int l,int r)
{node[nums].u=a;node[nums].v=b;node[nums].l=l;node[nums].r=r;node[nums].next=head[a];head[a]=nums++;
}
int dfs(int st,int l,int r)
{if(l>r)return 0;vis[st]=1;if(st==n)return 1;for(int i=head[st];i!=-1;i=node[i].next){if(vis[node[i].v])continue;if(node[i].l<=l&&node[i].r>=r){if(dfs(node[i].v,l,r))return 1;}}return 0;
}
int main()
{int i,a,b,l,r;int fl[maxn];int fr[maxn];while(~scanf("%d%d",&n,&m)){init();for(i=1;i<=m;i++){scanf("%d%d%d%d",&a,&b,&l,&r);add(a,b,l,r);add(b,a,l,r);fl[i]=l;fr[i]=r;}int ans=-1;sort(fl,fl+m+1);sort(fr,fr+m+1);for(i=1;i<=m;i++){int l=1;int r=m+1;int mid=(l+r)/2;while(l<r){memset(vis,0,sizeof(vis));if(dfs(1,fl[i],fr[mid]))l=mid+1;else r=mid;mid=(l+r)/2;}mid=mid-1;if(fl[i]<=fr[mid]){ans=max(ans,fr[mid]-fl[i]+1);}}if(ans==-1){printf("Nice work, Dima!\n");continue;}printf("%d\n",ans);}return 0;
}