枚举区间的左端点， 然后那些左端点比枚举的左端点小的都按右端点排序然后并查集去check
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;const int N = 3e3 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;int n, m, tot, ans;
int fa[N];
struct Edge {
bool operator < (const Edge& rhs) const {
return l < rhs.l;
}
int a, b, l, r;
} e[N], tmp[N];int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
}int Merge(int id) {
int u = tmp[id].a, v = tmp[id].b;
fa[getRoot(u)] = getRoot(v);
if(getRoot() == getRoot(n)) return tmp[id].r;
else return -;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++)
scanf("%d%d%d%d", &e[i].a, &e[i].b, &e[i].l, &e[i].r);
sort(e + , e + + m);
for(int i = ; i <= m; i++) {
for(int j = ; j <= n; j++) fa[j] = j;
tmp[++tot] = e[i];
int ret = Merge(tot);
for(int j = ; j < tot && ret == -; j++) ret = Merge(j);
if(~ret) ans = max(ans, min(e[i].r, ret) - e[i].l + );
for(int j = tot; j > ; j--)
if(tmp[j].r > tmp[j - ].r) swap(tmp[j], tmp[j - ]);
}
if(ans) printf("%d\n", ans);
else puts("Nice work, Dima!");
return ;
}/*
*/
