cats 的最小生成树

Problem Description

cats 有一个有 $n$ 个点，$m$ 个边的可能有重边的无向图。边有边权，其中第 $i$ 条边的边权为 $i$。 在一次操作中，cats 会找出这个图的最小生成树，然后将图中所有属于最小生成树的边移除。cats 会不断重复以上操作直到图不连通为止。 现在，你需要告诉 cats 图中的每一条边是在第几次操作中被移除的。若一条边在操作结束时未被移除，你需要输出 $-1$。 可以证明在以上条件下，cats 每次选择的最小生成树一定是唯一的。 注：一个有 $n$ 个点的图的最小生成树即为这个图的所有的包含全部 $n$ 个点和刚好 $n-1$ 条边的连通子图中使子图所有边的边权总和最小的子图。

Input

第一行一个整数 $T$ $(1\leq T\leq 1000)$，表示测试数据的组数。 每组测试数据的第一行包含两个整数 $n,m$ $(2\leq n\leq 10^5,1\leq m\leq 3\cdot 10^5)$，表示图中点和边的个数。 接下来 $m$ 行，每行两个整数 $u_i,v_i$ $(1\leq u_i,v_i\leq n,u_i\neq v_i)$，表示第 $i$ 条边连接的两个点。第 $i$ 条边的边权为 $i$。 保证所有测试数据的 $n$ 之和不超过 $5\cdot 10^5$，保证所有测试数据的 $m$ 之和不超过 $1.5\cdot 10^6$。

Output

对于每组测试数据，输出一行 $m$ 个整数。对于第 $i$ 个数，若第 $i$ 个边在第 $x$ 次操作中被移除，你需要输出 $x$。若第 $i$ 个边在操作结束时未被移除，你需要输出 $-1$。

Sample Input

3
3 3
1 2
2 3
3 1
3 3
1 2
2 1
2 1
4 6
1 2
1 2
1 3
2 3
1 4
3 4

Sample Output

1 1 -1
-1 -1 -1
1 2 1 2 1 2

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）