题目描述

译自 POI 2010 Stage 3. Day 2「Bridges」

给定一个 $n$ 个点的无向图，每条边的两个方向各有一个权值，求一条从 $1$ 号点出发，恰经过所有边一次并回到 $1$ 号点的路线，使得权值的最大值最小。

输入格式

第一行两个整数 $n, m$，分别表示点的数量和边的数量。点从 $1$ 到 $n$ 编号，边从 $1$ 到 $m$ 编号。

接下来 $m$ 行每行有四个整数 $a_i, b_i, l_i, p_i$，表示第 $i$ 条边连接 $a_i, b_i$，且从 $a_i$ 到 $b_i$ 的权值为 $l_i$，从 $b_i$ 到 $a_i$ 的权值为 $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

最优路线为
$1 \xrightarrow{4} 4 \xrightarrow{4} 3 \xrightarrow{4} 2 \xrightarrow{4} 1$，
最大权值为 $4$。

数据范围与提示

对于 $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$。