返祖能到达的最早时刻

难度：T4

【知识点：low-link不变量】

前置知识：low-link不变量及其冻结前置单元。

题目描述与输入

第一行$n$ $m$，随后$m$行无向边$u$ $v$ $w$，$w=1$；最后一行$f$。先删除编号$f$的那一条边，$f=0$表示不删除。再按保留边的原输入邻接顺序和最小未访问顶点顺序构建$DFS$森林，输出新的$low$值。

输出

一行按顶点编号输出$low$。

数据范围

$1 \le n \le 80$，$0 \le m \le 500$，$w=1$。无向多重图。按输入邻接顺序$DFS$，连通块按最小未访问编号启动，时间从$1$连续编号。 $0 \le f \le m$。删除不改变其余边的相对顺序。

样例输入

4 4
1 2 1
2 3 1
3 1 1
3 4 1
0

样例输出

1 1 1 4

样例说明

样例$f=0$不封闭道路；$low$按顶点顺序为$1$、$1$、$1$、$4$。