题目描述
注意这题和在集训队 OJ 上的版本不同,数据范围部分分都有改动,并且为了卡掉乱搞,这里需要多测
马宝锅老师和一位年轻人准备在一张 n 个点、m 条边的无向图上比武。由于年轻人担心马宝锅老师骂他不讲武德,因此他需要改进一下比赛场地。
对于每条无向边,有两个参数:地板的光滑度 ai 以及两侧墙的光滑度 bi。年轻人需要选出恰好 k 条边,并删掉剩下所有的边。
为了不让马宝锅老师会方便逃跑,年轻人要求这 k 条边不形成环。此外,为了不让马宝锅老师摔倒来讹他,年轻人要求这 k 条边的 ai 之和乘以 bi 之和尽量小。
由于他还没有确定 k 到底是多少,因此你需要对于 1≤k<n 的所有 k 求出答案。
输入格式
第一行一个正整数 T,表示数据组数。
对于每组数据,第一行两个正整数 n,m,表示点数和边数。
接下来 m 行每行四个正整数 ai,bi,ui,vi,表示这条边的地板光滑度、墙的光滑度以及连接的两个点。
输出格式
对于每组数据输出一行 n−1 个数字,第 i 个数字表示 k=i 时的答案。
样例
1
4 5
2 3 1 2
5 6 1 3
6 1 3 4
4 1 3 4
2 1 2 4
2 12 40
k=1 时,选的边是 (2,4)。
k=2 时,选的边是 (2,4),(3,4)。
k=3 时,选的边是 (2,4),(3,4),(1,2)。
数据范围与提示
对于所有数据,保证 n−1≤m≤1500,∑m2≤2.5×106,1≤ui,vi≤n,ui=vi,1≤ai,bi≤2×106,输入的图是连通图,并且对于任意的 1≤i<j≤m,都有 ai=aj 或者 bi=bj,即二元组 (ai,bi) 两两不同。
subtask1(10pts):n,m≤20,T=1
subtask2(20pts):n−1=m,即输入的边构成一棵树,且 n≤50
subtask3(20pts):n,m≤50
subtask4(20pts):n−1=m,即输入的边构成一棵树。
subtask5(30pts): 无特殊限制。