虚空思考一早上试图优化暴力，结果发现复杂度分析错了这个是正解，严肃浪费 4h /hec

显然考虑 kruskal 重构树。

对于给定的图按最小生成树的方式建一遍重构树，于是补图边权转化成树上的 LCA。

我们要求的问题就是对于每一条边，两个端点在补图上的瓶颈路。

一样考虑对补图跑一个重构树。

边太多了不能直接建，考虑优化建图。

回到 kruskal 的过程，我们按照边权从小往大进行枚举，而这里边权是原来树上的 LCA。

所以我们考虑自底向上枚举树上的点，以其作为 LCA 时的边思考怎么进行加入。

首先底下的边加完以后变成若干个连通块分别划分在左右两侧，此时你可以对左右两侧的连通块进行连边。

考虑怎么合并连通块。

很容易得到一个暴力合并的做法，选择两个连通块，遍历内部的所有点对，如果原图存在边则不管，否则合并连通块然后退出。

这么做的时间复杂度是？

合并 $O(n)$ 次。

无法合并最多 $O(m)$ 次。

这个暴力是线性的！

然后做完了啊，合并连通块集合直接 dsu 处理即可。

时间复杂度应该是 $O(n\log n)$ 的。

注意不要写退化。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
struct vec{
    int u,v,w;
};
vector<vec>vct,vct2;
bool cmp(vec a,vec b){
    return a.w<b.w;
}
unordered_map<int,bool>mp;
int fa[N<<1];
int v[N<<1];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void initdsu(int n){
    for(int i=1;i<=n;i++)
    fa[i]=i;
}
vector<int>ve[N<<1];
vector<int>e[N];
vector<int>d[N];
bool del[N];
int fa2[N];
int ver[N];
int vs=114;
void down(int x){
    if(ver[x]==vs)return;
    ver[x]=vs;
    fa2[x]=fa[x];
}
int find2(int x){
    down(x);
    return fa2[x]==x?x:fa2[x]=find2(fa2[x]);
}
void merge(int x,int y){
    x=find2(x),y=find2(y);
    if(x==y)return;
    if(d[x].size()>d[y].size())swap(x,y);
    for(int i:d[x])d[y].push_back(i);
    del[x]=1;
    fa2[x]=y;
}
int qwq[N<<1];
void dfs(int X){
    if(ve[X].empty()){
        qwq[X]=X;
        return;
    }
    for(int i:ve[X])
    dfs(i);
    vector<pair<int,int>>add;
    vs++;
    for(int x:e[qwq[ve[X][0]]]){
        if(!del[x])
        for(int y:e[qwq[ve[X][1]]])
        if(!del[y]&&find2(x)!=find2(y))
        for(int i:d[x]){
            bool flg=0;
            for(int j:d[y])
            if(!mp[(i<<30)|j]){
                flg=1;
                fa2[find2(x)]=find2(y);
                vct2.push_back({i,j,-1});
                add.push_back({x,y});
                break;
            }
            if(flg)break;
        }
    }
    vs++;
    for(pair<int,int>o:add)
    merge(o.first,o.second);
    int x=qwq[ve[X][0]];
    int y=qwq[ve[X][1]];
    if(e[x].size()>e[y].size())swap(x,y);
    qwq[X]=y;
    for(int i:e[x])
    if(!del[i])
    e[y].push_back(i);
}
int mi[25][N<<1];
int dfn[N<<1],dfnn;
int get(int u,int v){
    if(dfn[u]<dfn[v])return u;
    return v;
}
void dfsiz(int x,int fa){
    dfn[x]=++dfnn;
    mi[0][dfn[x]]=fa;
    for(int i:ve[x])
    dfsiz(i,x);
}
int lca(int u,int v){
    if(u==v)return u;
    u=dfn[u],v=dfn[v];
    if(u>v)swap(u,v);
    int g=__lg(v-u);
    return get(mi[g][u+1],mi[g][v-(1<<(g))+1]);
}
struct fish{
    int u,v;
};
vector<fish>q;
void init(int n){
    dfnn=0;
    vct.clear();
    vct2.clear();
    mp.clear();
    initdsu(n<<1);
    for(int i=1;i<=(n<<1);i++)
    ve[i].clear(),v[i]=0;
    for(int i=1;i<=n;i++)
    e[i].clear(),d[i].clear();
    for(int i=1;i<=n;i++)
    e[i].push_back(i),
    d[i].push_back(i),
    del[i]=0;
}
/*
1 0
10 31
1 4 31
9 1 1
2 3 5
2 5 19
9 6 26
10 4 30
2 4 29
4 6 2
8 6 8
6 5 15
4 8 6
8 7 24
4 5 12
10 7 20
9 8 27
4 7 18
3 4 3
7 5 9
10 8 4
8 1 23
7 2 13
1 2 11
7 6 28
7 1 22
6 3 17
8 3 21
1 5 10
2 9 16
5 8 7
5 3 14
3 9 25
*/
void solve(){
    q.clear();
    int n,m,in_n;
    cin>>n>>m;in_n=n;
    init(n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        vct.push_back({u,v,w});
        mp[(u<<30)|v]=mp[(v<<30)|u]=1;
        q.push_back({u,v});
    }
    sort(vct.begin(),vct.end(),cmp);
    for(vec i:vct){
        if(find(i.u)==find(i.v))continue;
        i.u=find(i.u);
        i.v=find(i.v);
        n++;
        fa[i.u]=n;
        fa[i.v]=n;
        ve[n].push_back(i.u);
        ve[n].push_back(i.v);
        v[n]=i.w;
    }
    initdsu(n);
    dfs(n);
    dfsiz(n,0);
    for(int i=1;i<=20;i++)
    for(int j=1;j+(1<<i)-1<=n;j++)
    mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
    for(int i=0;i<vct2.size();i++)
    vct2[i].w=v[lca(vct2[i].u,vct2[i].v)];
    sort(vct2.begin(),vct2.end(),cmp);
    initdsu(n);
    n=in_n;
    for(int i=1;i<=(n<<1);i++)
    ve[i].clear(),v[i]=0;
    for(vec i:vct2){
        if(find(i.u)==find(i.v))continue;
        i.u=find(i.u);
        i.v=find(i.v);
        n++;
        fa[i.u]=n;
        fa[i.v]=n;
        ve[n].push_back(i.u);
        ve[n].push_back(i.v);
        v[n]=i.w;
    }
    dfnn=0;
    dfsiz(n,0);
    for(int i=1;i<=20;i++)
    for(int j=1;j+(1<<i)-1<=n;j++)
    mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
    for(fish i:q)
    cout<<v[lca(i.u,i.v)]<<' ';
    cout<<'\n';
}
signed main(){
    int t,g;
    cin>>t>>g;
    while(t--)solve();
    return 0;
}
//『如垃圾般崩落的某人』

//『燃烧旺盛的火焰』

//『止不住的悲鸣』『暴风雨之夜』『燃烧坠落的飞空艇』『后悔』

//「──啊……」

// 好几个片段的意象，瞬间横穿过眼前而去。

// 好几个片段的记忆，瞬间敲动心中的水面后消失。

//『灰色的大地』『想活下去』『不可取代的目的』『无明之夜』『纳莎妮亚』『缠上脚踝的无数只手』『无法实现的梦想』『终结的现实』『如同笑声般的尖叫』『无尽的洞穴』『穆罕默达利‧布隆顿随军研究医师』『渴望故乡的声音』『遗迹兵器莫乌尔涅』『想归返的强烈心情』『无边无际的灰色沙漠』『织光的第十四兽』『心在灼烧』『连结』『束缚』『吞噬』『然后』