4467: 「POI2010」桥 Bridges
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**译自 POI 2010 Stage 3. Day 2「[Bridges](https://szkopul.edu.pl/problemset/problem/gh2Yj6Ckrt4Lo_RojONuljuC/site/?key=statement)」**
给定一个 $n$ 个点的无向图，每条边的两个方向各有一个权值，求一条从 $1$ 号点出发，恰经过所有边一次并回到 $1$ 号点的路线，使得权值的最大值最小。
输入
第一行两个整数 $n,m$ ，分别表示点的数量和边的数量。点从 $1$ 到 $n$ 编号，边从 $1$ 到 $m$ 编号。
接下来 $m$ 行每行有四个整数 $a_i,b_i,l_i,p_i $ ，表示第 $i$ 条边连接 $a,b$ ，且从 $a$ 到 $b$ 的权值为 $l_i$ ，从 $b$ 到 $a$ 的权值为 $p_i$。
输出
如果原图不存在这样的路线，输出 ```NIE``` 。否则，应该输出两行，第一行表示路线中权值最大值的最小值，第二行有 $m$ 个整数，依次表示你选择的路线的边。如果有多条这样的路线，可以输出任意一条。
样例输入 复制
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4样例输出 复制
4
4 3 2 1提示
数据范围：对于 $100\%$ 的数据， $2 \le n \le 1000,1 \le m \le 2000 , 1 \le a_i,b_i \le n,a_i \neq b_i,1 \le l_i,p_i \le 1000$ 。 Translated & SPJ by vincent163