Migrated from Lutece 2528 猛男修树 · 二

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

UESTC 的集训室门前有一排树，其中第一棵是线段树，第二棵是平衡树，第三棵是动态树……

魔法少女 Sugarii 的树魔法出了些 bug——一些树的枝条长到了别的树上。

现在这些树变成了由 $n$ 个结点和 $m$ 条边构成的无向图。

Sugarii 找到了猛男 Fatdog_jo 来帮忙剪掉一些不该存在的边，但是 Fatdog_jo 并不想思考哪些边应该留下，他会按照给出边的顺序依次剪掉所有的边。

为了犒劳 Fatdog_jo，Sugarii 在每个结点上都放上了一包狗粮（？）。Fatdog_jo 在剪掉一条边 $(u, v)$ 前，会先在结点 $u, v$ 所在的连通块内选一包狗粮吃掉，并且他会贪心地选所在节点编号最大的那包狗粮。如果这个连通块内的每个结点上都没有狗粮了，Fatdog_jo 就会因为吃不到狗粮而罢工不干——他会直接跳过修剪这条边。

现在 Sugarii 想知道这些狗粮被 Fatdog_jo 吃掉的顺序。

Input

输入的第一行包含一个正整数 $T\ (1 \leq T \leq 10^5)$，表示有 $T$ 组测试数据。

每组测试数据的第一行包含两个正整数 $n, m\ (1 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5)$，表示图有 $n$ 个结点，$m$ 条边。

接下来的 $m$ 行每行包含两个正整数 $u, v\ (1 \leq u, v \leq n)$，表示结点 $u, v$ 之间有一条边相连。Fatdog_jo 将按照给出边的顺序依次剪掉这些边。

保证对于所有的 $T$ 组数据，有 $\sum n \leq 10^5, \sum m \leq 2 \times 10^5$。

Output

对于每组测试数据，输出 $m$ 行。

第 $i$ 行的数表示 Fatdog_jo 在修剪第 $i$ 条边前吃掉的狗粮的所在节点的编号，如果 Fatdog_jo 没有吃到狗粮并跳过了这条边，输出 $0$。

Samples

2
5 5
2 1
5 5
5 2
2 3
3 5
10 10
7 2
9 5
10 7
5 7
10 2
1 4
10 7
5 6
2 5
1 6

5
3
2
0
0
10
9
7
6
5
4
0
2
0
1

Resources

2021 UESTC ICPC Training for Data Structures