其实这题有两种建模方法，因为我都写了，所以两个都讲好了。
一眼二分答案，转为判定性问题：
给定含有无向边和有向边的图 \(G\)，判断是否存在欧拉回路。
首先先判掉存在 \(u\)，\(2\nmid \text{deg}_u\) 的情况。
不能简单地根据度数判断，考虑网络流建模。
- 方法 \(1\)：
考虑到对于每条边 \(e_i\)，最多给一个点会提供 \(1\) 的出度。
然后对于一个点 \(v_i\)，最后它的出度一定为 \(\frac{\text{deg}_{v_i}}{2}\)。
这启示我们将边和点两两匹配。那我们对于 \(S\to e_i\)，连流量为 \(1\) 的边，表示这条边最多匹配 \(1\) 个点给出度。对于 \(v_i\to T\)，连流量为 \(\frac{\text{deg}_{v_i}}{2}\) 的边，表示这个点要匹配这么多条边给它出度。对于一条边 \(e_i=(u,v)\)，如果单向，不妨设 \(u\to v\)，那么直接 \(e_i\) 向 \(u\) 流 \(1\)。否则 \(e_i\) 向 \(u,v\) 分别流 \(1\)，表示 \(e_i\) 既可以匹配 \(u\)，也可以匹配 \(v\)。
然后我们跑最大流，判断是否满流即可。最后构造方案可以在残量网络上根据是否有 \(e_i\to u_i\) 建图跑欧拉回路。
- 方法 \(2\)：
先给每条无向边随意定一个方向，假定是 \(u\to v\)，计算此时每个点的入度 \(\text{in}_u\) 和出度 \(\text{out}_u\)。
那么对于 \(\text{in}_u>\text{out}_u\) 的点，我们将 \(S\) 向 \(u\) 连流量 \(\frac{\text{in}_u-\text{out}_u}{2}\) 的边。表示它需要流入这么多流量才能使 \(\text{in}_u=\text{out}_u\)。
同理，对于 \(\text{in}_v<\text{out}_v\) 的点，我们将 \(v\) 向 \(T\) 连流量 \(\frac{\text{out}_v-\text{in}_v}{2}\) 的边。表示它需要流出这么多流量才能使 \(\text{in}_v=\text{out}_v\)。
对于无向边 \((u,v)\)，我们假定了 \(u\to v\)。那么 \(v\to u\) 连一条流量为 \(1\) 的边，表示我们可以反悔。
然后同样跑最大流，判断是否满流，然后构造有向图跑欧拉回路即可。
方法 \(2\) 的代码，自以为写得十分清新。
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define pc putchar
#define pi pair<int, int>
#define tu3 tuple<int, int, int>
#define tu4 tuple<int, int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int maxn = 5e3 + 100;
const int maxm = 5e4 + 200;
struct edg { int u, v, w1, w2; } ed[maxn];
struct edge { int to, nxt, w; } e[maxn + maxm];
struct node { int to, nxt, w; } g[maxm];
int n, m, s, t, tot = 1, l, r, ans = -1;
int head[maxn], fa[maxn], sz[maxn], deg[maxn], id[maxm], dep[maxn], vis[maxm];
void add_edge(int u, int v, int w) { e[++tot] = (edge) { v, head[u], w }, head[u] = tot; }
void add_edg(int u, int v, int w) { g[++tot] = (node) { v, head[u], w }, head[u] = tot; }
void add_flow(int u, int v, int w) { add_edge(u, v, w), add_edge(v, u, 0); }
int getf(int x) { return fa[x] == x ? x : fa[x] = getf(fa[x]); }
void mrg(int x, int y) {
x = getf(x), y = getf(y);
if (x == y) return;
fa[x] = y, sz[x] += sz[y];
}
bool bfs() {
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[s] = 1, q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (e[i].w && !dep[v])
dep[v] = dep[u] + 1, q.push(v);
}
}
return dep[t];
}
int dfs(int u, int in) {
if (u == t) return in;
int out = 0;
for (int i = head[u]; i && in; i = e[i].nxt) {
int v = e[i].to;
if (e[i].w && dep[v] == dep[u] + 1) {
int res = dfs(v, min(in, e[i].w));
in -= res, out += res;
e[i].w -= res, e[i ^ 1].w += res;
}
}
if (!out) dep[u] = 0;
return out;
}
bool chk(int x) {
for (int i = 1; i <= n; i++) deg[i] = 0;
for (int i = 0; i <= t; i++) head[i] = 0;
tot = 1;
for (int i = 1; i <= m; i++) {
int u = ed[i].u, v = ed[i].v;
if (ed[i].w1 <= x) deg[u]--, deg[v]++;
if (ed[i].w2 <= x) id[i] = tot + 1, add_flow(v, u, 1);
}
for (int i = 1; i <= n; i++)
if (deg[i] & 1) return 0;
int sum = 0;
for (int i = 1; i <= n; i++) {
if (deg[i] > 0) sum += deg[i] / 2, add_flow(s, i, deg[i] / 2);
else add_flow(i, t, -deg[i] / 2);
}
while (bfs()) sum -= dfs(s, 1e9);
return sum == 0;
}
stack<int> tp;
void eul(int u, int lst) {
for (int i = head[u]; i; i = head[u]) {
head[u] = g[i].nxt;
eul(g[i].to, g[i].w);
}
if (lst) tp.push(lst);
}
int main() {
n = read(), m = read(), t = n + 1;
for (int i = 1; i <= m; i++) {
ed[i] = (edg) { read(), read(), read(), read() };
if (ed[i].w1 > ed[i].w2) swap(ed[i].u, ed[i].v), swap(ed[i].w1, ed[i].w2);
l = max(l, ed[i].w1), r = max(r, ed[i].w2), mrg(ed[i].u, ed[i].v);
}
int c1 = 0, c2 = 0;
for (int i = 1; i <= n; i++)
if (getf(i) == i) c1++, c2 += (sz[i] == 1);
if (c2 >= 1 && c2 != c1 - 1) return puts("NIE"), 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (chk(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
if (ans == -1) return puts("NIE"), 0;
write(ans), puts("");
chk(ans);
tot = 0;
for (int i = 1; i <= n; i++) head[i] = 0;
for (int i = 1; i <= m; i++) {
if (ed[i].w2 > ans) add_edg(ed[i].u, ed[i].v, i);
else {
if (e[id[i]].w) add_edg(ed[i].u, ed[i].v, i);
else add_edg(ed[i].v, ed[i].u, i);
}
}
eul(1, 0);
while (tp.size()) write(tp.top()), pc(' '), tp.pop();
return 0;
}