Description：

给一个无向图，边正反走边权不同，找一条最大边权最小的欧拉回路。

$1\leqslant n\leqslant 1000,1\leqslant m\leqslant2000$

Solution：

根据有向图存在欧拉回路的充要条件得，只要图联通并且每个点入度等于出度，那么就存在一个欧拉回路。

看到最大值最小可以二分，把二分后合法的边都加进去，那么图中有一些边有向，另一些边无向，问题就在于给无向边定向使得每个点入度等于出度。

可以先把无向边随便定向，于是我们就得到了一个有向图，需要反转其中的一些边使得每个点入度 $=$ 出度，有一个非常神奇的建图就是把一条容量为 $1$ 的边被流过看成把这条边反转，那么流过一条边会使起点出度 $-$ 入度减二，终点出度 $-$ 入度加二，那么设 $d[i]$ 为第 $i$ 个点出度 $-$ 入度，若 $d[i]>0$ ，那么说明这个点需要有 $\frac{d[i]}2$ 的流量流入，否则说明这个点需要 $\frac{d[i]}2$ 的流量流出，按照这个分别和源汇连边即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

#define MAXM 2010

struct edges

{

	int u,v,a,b;

}es[MAXM];

int ind[MAXN],oud[MAXN];

struct edge

{

	int to,nxt,f;

}e[(MAXM + MAXN) << 1];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f)

{//cout << a << " " << b << " " << f << endl;

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

void edge_init()

{

	edgenum = 0;

	memset(lin,-1,sizeof(lin));

	memset(ind,0,sizeof(ind));

	memset(oud,0,sizeof(oud));

	return;

}

int ch[MAXN];

#define INF 0x3f3f3f3f

int s,t;

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

bool check(int w)

{//cout << w << " : " << endl;

	edge_init();

	for(int i = 1;i <= m;++i)

	{

		if(es[i].a > w && es[i].b > w)return false;

		if(es[i].a > w && es[i].b <= w){++oud[es[i].v];++ind[es[i].u];continue;}

		if(es[i].a <= w && es[i].b > w){++oud[es[i].u];++ind[es[i].v];continue;}

		add(es[i].u,es[i].v,1);

		++ind[es[i].v];++oud[es[i].u];

	}

	for(int i = 1;i <= n;++i)

		if((ind[i] - oud[i]) % 2 != 0)return false;

	s = n + 1;t = s + 1;

	int sum = 0;

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] != oud[i])

		{

			if(ind[i] > oud[i])

			{

				sum += ind[i] - oud[i];

				add(i,t,(ind[i] - oud[i]) / 2);

			}

			else add(s,i,(oud[i] - ind[i]) / 2);

		}

	}

	int res = dinic();

	//cout << sum << " " << res << endl << endl;

	return (res * 2 == sum);

}

int main()

{

	scanf("%d%d",&n,&m);

	int lowbound = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);

		lowbound = max(lowbound,min(es[i].a,es[i].b));

	}

	int l = lowbound,r = 1001,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	if(l != 1001)cout << l << endl;

	else puts("NIE");

	return 0;

}