Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB
Statistics

【题目背景】

道情非是等閒情,旣識天機不可輕。

先把世情齊放下,次將道理細研精。

未煉還丹先煉性,未修大藥且修心。

心修自然丹信至,性淸自然藥材生。

藥材生,緊加功。雷聲隱隱震虛空。

電光灼處尋眞種,風信來時覓本宗。

霞光萬道籠金鼎,紫雲千丈罩天門。

若還到此休驚怕,穩把元. 神守洞門。
.
如猫捕鼠兎逢鷹,急急着力又加勤。

萬般景象皆非類,一顆紅光是至眞。

此箇紅光是春意,其中有若明窗塵。

中懸一點先天藥,遠似葡萄近似金。

到此全憑要謹愼,絲毫念起喪天眞。

待他一點自歸伏,身中化作四時春。

一片白雲香一陣,一番雨過一番新。

終日綿綿如醉漢,悠悠只等洞中春。

遍體陰精都剝盡,化作純陽一塊金。

此時氣絕如小死,打成一片是全眞。
到此功成纔了當,卻來塵世積功勛。

行滿功成天命詔,陽神出現了眞靈。

此言休向非人說,不逢達者莫輕論。

其中切切通玄理,此眞之外更無眞。

收拾行囊牢封固,他日成功可印心。

可印心,五十二句要君尋。

若有虛言遭天譴,說與非人鞭喪身。

——张三丰《道情歌》

【题目描述】

给定一张 $n$ 个点 $m$ 条边的无向图(可能存在重边)。

已知第 $i$ 条边的权值 $w_i \in [l_i, r_i]$,且 $\{w_m\}$ 是 $1$ ∼ $m$ 的排列。

在前 $n − 1$ 条边构成最小生成树的前提下,最小化 $\{w_m\}$ 的字典序。

【输入格式】

第一行两个整数 $n$, $m$。

接下来 $m$ 行,第 $i$ 行四个整数 $u_i$, $v_i$, $l_i$, $r_i$,表示第 $i$ 条边为 $(u_i, v_i)$。

【输出格式】

如果不存在合法的 $\{w_m\}$,输出一行一个整数 $−1$。

否则,输出一行 $m$ 个整数 $w_1, w_2,... , w_m$。

【样例1输入】

4 5
1 3 1 3
1 4 2 4
1 2 1 4
2 3 3 3
2 3 3 5

【样例1输出】

1 4 2 3 5

【样例2输入】

3 3
1 2 2 3
2 3 2 3
1 3 1 3

【样例2输出】

-1

【数据范围】

保证 $1 ≤ n − 1 ≤ m ≤ 3500, 1 ≤ ui < vi ≤ n, 1 ≤ li ≤ ri ≤ m$。

保证给出的前 $n − 1$ 条边构成原图的一棵生成树。