最小生成树专题

生成树

定义连通无向连通图 $G$ 的生成树是有 $G$ 的一个树子图。

最小生成树

算法

一般有三种算法可以用来求最小生成树，实际做题时应根据题目灵活选用适合的算法。

Kruskal

将边从小到大排序，依次遍历，如果当前边的两个端点之间没有连通就加入这条边，最后加入的边构成的就是最小生成树。

用并查集维护连通性。

复杂度 $O(m\log m)$ 。

模板代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 5005;
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int u,int v){
    fa[find(u)]=find(v);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;

    vector<tuple<int,int,int>> edges;
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        edges.push_back({w,u,v});
    }
    sort(edges.begin(),edges.end());

    int ans = 0,cnt = 0;
    for(auto [w,u,v]:edges){
        if(find(u)!=find(v)){
            unite(u,v);
            ans += w;
            ++cnt;
        }
    }
    if(cnt != n-1){ // 图不连通
        cout << "orz\n";
        return 0;
    }
    cout << ans << '\n';
    return 0;
}

例题：

QOJ# 9904. 最小生成树（题解）

Prim

把节点分为「未加入」和「已加入」两类，开始有一个任意节点在「已加入」中，其余都是「未加入」的。

每次从「未加入」的节点中，找到一个与「已加入」节点之间边权最小的节点，将该节点加入「已加入」中，并将该边加入最小生成树。

重复 $(n-1)$ 次就得到了最小生成树。

实现方面，类似 dijkstra，用一个 priority_queue 来找到这个最小的边权，复杂度 $O((n+m)\log n)$ 。

模板代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 5005;
vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m; cin>>n>>m;
    
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    int cnt=0, ans=0;

    memset(dis, 0x3f, sizeof(dis));
    dis[1]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,1});
    
    while(pq.size()){
        auto [d,u] = pq.top(); pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        cnt++, ans -=d; 
        for(auto [v,w]:G[u]){
            if(dis[v]>w){
                dis[v] = w;
                pq.push({-dis[v], v});
            }
        }
    }


    if(cnt != n){ // 图不连通
        cout << "orz\n";
        return 0;
    }
    cout << ans << '\n';
    return 0;
}

Boruvka

最开始每个点都是孤立的连通块，每一轮对于每个连通块，找到该连通块往外的最小边，将这些最小边加入（如果该边两端点不在同一个连通块中），不断重复直至没有新边加入，最后得到的就是最小生成树（森林）。

最多进行 $O(\log n)$ 轮，每次暴力找最小边复杂度 $O(m)$ ，因此一般图上 Boruvka 算法的复杂度是 $O(m\log n)$ 的。

模板代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 5005;
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int u,int v){
    fa[find(u)]=find(v);
}
int mn[N];

const int M = 2e5+5;
struct Edge{
    int u,v,w;
}edges[M];
bool used[M];


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;

    edges[0].w = 1e9;
    for(int i=1;i<=m;i++){
        cin>>edges[i].u>>edges[i].v>>edges[i].w;
    }
    
    bool change = 1; // 是否有加边
    int cnt = 0, ans = 0;
    while(change){ // 没有加边就退出
        change = 0;
        for(int i=1;i<=n;i++)mn[i]=0;
        for(int i=1;i<=m;i++){
            int u = find(edges[i].u), v = find(edges[i].v);
            if(u == v)continue;
            if(edges[i].w < edges[mn[u]].w)mn[u] = i;
            if(edges[i].w < edges[mn[v]].w)mn[v] = i;
        }

        for(int i=1;i<=n;i++){
            if(mn[i] && !used[mn[i]]){
                change = 1;
                used[mn[i]]=1, cnt++;
                ans += edges[mn[i]].w;
                unite(edges[mn[i]].u, edges[mn[i]].v);
            }
        }
    }

    if(cnt != n-1){ // 图不连通
        cout << "orz\n";
        return 0;
    }
    cout << ans << '\n';
    return 0;
}

例题：

CF888G. Xor-MST

给定 $a_1,a_2,\ldots,a_n$ 和一个完全图 $G$ ， $u$ 到 $v$ 之间连边的边权是 $a_u \oplus a_v$ 。求 $G$ 的最小生成树大小。

$n\le 2\times 10^5, a_i<2^{30}$ 。

我们希望能够快速求出连通块向外连边的最小值。

求每个点往外的边的最小值可以使用 01-Trie，先将所有 $a_i$ 加入 Trie，然后一个一个连通块处理，每次把连通块内的权从 Trie 删除，然后再求每个点往外边权的最小值。

实现注意两点：

为了维护连通块内的节点，在并查集时启发式合并当前集合内的节点。
Trie 查找最小值还需要知道是哪个节点，如果 $\{a_n\}$ 中有重复的这个不是很好解决，但是我们发现对 $\{a_n\}$ 去重不会影响答案（因为相同点权的点可以以 $0$ 的代价连接在一起），所以 $\{a_n\}$ 互不相同，我们只需要在 Trie 的叶子节点记录该叶子对应的是哪个点就能解决问题。

这样每一轮的复杂度就是 $O(n \log V)$ ，其中 $V=\max_{i=1}^n a_i$ 。

因此问题就在 $O(n \log V \log n)$ 复杂度内解决了。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define all(x) (x).begin(),(x).end()
const int N = 2e5+5;

struct Trie{
    int ch[N*30][2],val[N*30],cnt[N*30];
    int tot=1;
    void insert(int x,int id){
        int u = 1;
        for(int i=29;i>=0;i--){
            int c = (x>>i)&1;
            if(!ch[u][c])ch[u][c]=++tot;
            u = ch[u][c];
            cnt[u]++;
        }
        val[u] = id;
    }
    void erase(int x){
        int u = 1;
        for(int i=29;i>=0;i--){
            int c = (x>>i)&1;
            u = ch[u][c];
            cnt[u]--;
        }
    }
    int min_xor(int x){
        int u = 1;
        for(int i=29;i>=0;i--){
            int c = ((x>>i)&1);
            if(ch[u][c] && cnt[ch[u][c]])u = ch[u][c];
            else u = ch[u][c^1];
        }
        return val[u];
    }
}t;

int a[N];

int fa[N];
vector<int> nodes[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int u,int v){
    u = find(u), v = find(v);
    if(u==v)return;
    if(nodes[u].size()<nodes[v].size())swap(u,v);
    fa[v]=u;
    nodes[u].insert(nodes[u].end(), all(nodes[v]));
    nodes[v].clear();
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n; cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    sort(a+1,a+1+n);
    n = unique(a+1,a+1+n) - a - 1;
    
    for(int i=1;i<=n;i++)t.insert(a[i], i);
    
    for(int i=1;i<=n;i++)fa[i]=i, nodes[i]={i};
    int cnt = 0; ll ans = 0;
    while(cnt < n-1){
        vector<pair<int,int>> edges;
        for(int i=1;i<=n;i++){
            if(i != find(i))continue;
            int min_val = 2e9;
            pair<int,int> min_edge = {-1,-1};
            for(auto u:nodes[i])t.erase(a[u]);
            for(auto u:nodes[i]){
                int v = t.min_xor(a[u]);
                if((a[u]^a[v]) < min_val){
                    min_val = a[u]^a[v];
                    min_edge = {u,v};
                }
            }
            edges.push_back(min_edge);
            for(auto u:nodes[i])t.insert(a[u], u);
        }

        for(auto [u,v]:edges){
            if(find(u) != find(v)){
                unite(u,v);
                ans += a[u]^a[v];
                ++cnt; 
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

次小生成树

可以证明，不论是非严格次小生成树还是严格次小生成树，和该图的某个最小生成树相比，最多替换一条边。

因此我们枚举替换的一条边 $(u,v)$ ，在原来的最小生成树上能替换的就是 $u - \operatorname{lca}(u,v) - v$ 这一段上的某个边。

对于非严格次小生成树来说，只需要替换这一段上的最大值即可，而对于严格次小生成树，如果最大值和替换的边权相同，需要寻找次大值。

所以要做的是树上路径查询最大值和次大值，因为树是静态的且只有查询，直接倍增即可。（当然也可以使用树链剖分等算法）

例题：
P4180 [BJWC2010] 严格次小生成树

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define all(x) x.begin(),x.end()

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct Edge{
    int u,v,w;
    bool operator<(const Edge& r)const{
        return w<r.w;
    }
};
const int N = 1e5+5;

vector<Edge> edges; 
vector<Edge> unused_edges; 
vector<pair<int,int>> G[N];   

struct DSU{
    int fa[N];
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void unite(int u,int v){
        fa[find(u)]=find(v);
    }
}dsu;

struct Node{
    int f,g;
};
Node merge(const Node& a,const Node& b){
    Node ret;
    ret.f=max(a.f,b.f);
    if(a.f==b.f)ret.g=max(a.g,b.g);
    if(a.f>b.f)ret.g=max(a.g,b.f);
    if(a.f<b.f)ret.g=max(a.f,b.g);
    return ret;    
}

int fa[N][30],dep[N];
Node val[N][30];
int lg[N];

void dfs(int u,int f,int ev){
    dep[u]=dep[f]+1;
    fa[u][0]=f;
    val[u][0].f=ev,val[u][0].g=-1;
    for(int i=1;i<=lg[dep[u]];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        val[u][i] = merge(val[u][i-1],val[fa[u][i-1]][i-1]);
    }
    for(auto e:G[u]){
        int v=e.first,w=e.second;
        if(v==f)continue;
        dfs(v,u,w);
    }
}

Node solve(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    Node ans{-1,-1};
    while(dep[u]<dep[v]){
        ans = merge(ans, val[v][lg[dep[v]-dep[u]]]);
        v = fa[v][lg[dep[v]-dep[u]]];
    }
    if(u==v)return ans;
    for(int i=lg[dep[u]];i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            ans = merge(ans,val[u][i]);
            ans = merge(ans,val[v][i]);
            u=fa[u][i];v=fa[v][i];
        }
    }
    ans = merge(ans,val[u][0]);
    ans = merge(ans,val[v][0]);
    return ans;
}

int main(){
    lg[1]=0;
    for(int i=2;i<N;i++)lg[i]=lg[i/2]+1;

    int n=read(),m=read();
    for(int i=0;i<m;i++){
        int u=read(),v=read(),w=read();
        if(u==v)continue;

        edges.push_back({u,v,w});
    }

    sort(all(edges));

    for(int i=1;i<=n;i++)dsu.fa[i]=i;

    ll MST = 0;
    
    for(auto e:edges){
        int u=e.u,v=e.v,w=e.w;
        if(dsu.find(u)!=dsu.find(v)){
            G[u].push_back({v,w});
            G[v].push_back({u,w});
            dsu.unite(u,v);
            MST+=w;
        }
        else unused_edges.push_back(e);
    }

    ll CMST = LONG_LONG_MAX;

    dfs(1,0,-1);
    
    for(auto e:unused_edges){
        int u=e.u,v=e.v,w=e.w;
        auto res = solve(u,v);
        if(res.f!=w){
            CMST = min(CMST, MST-res.f+w);
        }
        else if(res.g!=-1){
            CMST = min(CMST, MST-res.g+w);
        }
    }
    printf("%lld\n",CMST);
    return 0;       
}

最小生成树唯一性

一个图的最小生成树不唯一，当且仅当存在一条不在最小生成树上的边 $(u,v,w)$ ，在最小生成树 $u\sim v$ 的路径上存在一条边权恰好为 $w$ 的边。

因此我们可以用次小生成树的方法来判断最小生成树是否唯一。

事实上，如果对 Kruskal 算法进行一些小小的修改，可以用更少的代码完成判断。

在 Kruskal 算法中，对于边权相同的边，先不一个一个加入，而是判断是否会与前面已经加入的边形成环，然后再一个一个加入，若不会形成环的边数量和能加入的边的数量相同，说明最小生成树唯一。（否则说明有两条边权相同的边形成了环可以互相替代）

例题：
POJ1679 The Unique MST

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct Edge{int u,v,w;};
bool operator<(const Edge& lhs, const Edge& rhs){
    return lhs.w < rhs.w;
}

const int N = 105;
int fa[N];
int find(int x){return x==fa[x]?x:x=find(fa[x]);}
void unite(int u,int v){fa[find(u)]=find(v);}


void solve(){
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;

    vector<Edge> edges(m);
    for(int i=0;i<m;i++)cin>>edges[i].u>>edges[i].v>>edges[i].w;

    sort(edges.begin(), edges.end());

    int ans = 0;

    for(int l=0,r;l<m;l=r+1){
        r=l; // edges[l~r] 的边权都相同
        while(r<m && edges[r+1].w==edges[l].w)++r;


        int cnt1=0, cnt2=0;
        for(int i=l;i<=r;i++){
            if(find(edges[i].u) != find(edges[i].v)) cnt1 ++;
        }
        for(int i=l;i<=r;i++){
            if(find(edges[i].u) != find(edges[i].v)){
                cnt2 ++;
                unite(edges[i].u, edges[i].v);
                ans += edges[i].w;
            }
        }

        if(cnt1 != cnt2){
            cout << "Not Unique!\n";
            return;
        }
    }

    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int T; cin>>T;
    while(T--)solve();
    return 0;
}

练习：CF1108F. MST Unification

最小生成树反推原图

这些题目一般都会给定你一棵树，要求构造一个图，使得这棵树是图的一个最小生成树。

若要满足是最小生成树，需要满足对于新添加的边 $(u,v,w)$ ， $w$ 比树上 $u \sim v$ 之间路径的任意一条边边权都大。

因此，我们要求出所有点对 $(u,v)$ ，树上 $u\sim v$ 路径上边的最大值。

我们可以将最小生成树的边从小到大加入，每次连接的两个连通分量的节点之间都满足最小生成树路径上边权最大的边是加入的边，于是便可以快速的统计完每个点对。

这种快速统计每个点对之间路径最大值的方法和 Kruskal 重构树是等价的。
关于 Kruskal 重构树的内容详见后文。

练习：

判断某些边是否在一个最小生成树中

CF891C. Envy

给出一个 $n$ 个点 $m$ 条边的带权无向图，共 $q$ 次询问，每次给出 $k_i$ 条边，问这些边能否同时在一棵最小生成树上。

$n,m,q,\sum k_i \le 5\times 10^5$ 。

首先我们需要知道，若两条边 $e_i$ 和 $e_j$ 边权不同，那么「 $e_i$ 在一棵最小生成树上且 $e_j$ 在一颗最小生成树上」和「 $e_i, e_j$ 同时在一颗最小生成树上」是等价的。

考虑 Kruskal 的过程，因为 Kruskal 对边权相同的边谁先加入没有要求，所以在处理完边权 $\le k$ 的边后，无论选择了哪些边，图的连通性一定完全相同，所以考虑含有边权大的边的最小生成树时，无需关心边权更小的边是如何选择的，无论怎么选择都不会影响答案。

那么对于本题来说，每个询问就能拆分成若干个含有相同边权的子询问。

我们考虑如何处理是否存在一颗最小生成树，使得边权同为 $w$ 的边 $e_1,e_2,\ldots,e_k$ 同时在最小生成树上。

由刚刚我们可以知道，可以直接将边权小于 $w$ 的边在 Kruskal 过程中直接加入（因为连通性一定相同），然后只需检测这些边与之前的边和这些边之间是否会成环即可。

实现方面，用并查集实现加边，并离线处理每个子询问，子询问处理完后还需撤销。

复杂度 $O(m\log m + \sum k_i\log \sum k_i)$ 。

#include<bits/stdc++.h>
using namespace std;
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const int N = 5e5+5;

struct Query{
    int id;
    vector<int> q_edges;
};
vector<Query> qu[N];
bool ans[N];

struct Revdsu{
    int fa[N],sz[N];
    vector<pair<int&,int>> his;
    void init(int n){
        for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
        his.clear();
    }
    int find(int x){
        while(x!=fa[x])x=fa[x];
        return x;
    }
    void unite(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return;
        if(sz[u]<sz[v])swap(u,v);
        his.push_back({fa[v],fa[v]});
        his.push_back({sz[u],sz[u]});
        fa[v]=u;sz[u]+=sz[v];
    }
    int S(){return his.size();}
    void rev(int S){
        while(his.size()>S){auto [a1,a2]=his.back();his.pop_back();a1=a2;}
    }
}dsu;

struct Edge{int u,v,w;}edges[N];
vector<pair<int,int>> ev[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m; cin>>n>>m;
    dsu.init(n);

    int maxw = 0;
    for(int i=1;i<=m;i++){
        cin>>edges[i].u>>edges[i].v>>edges[i].w;
        ev[edges[i].w].push_back({edges[i].u,edges[i].v});
        maxw = max(maxw, edges[i].w);
    }

    int q;cin>>q;
    for(int i=1;i<=q;i++){
        ans[i]=1;
        int k;cin>>k;
        while(k--){
            int e; cin>>e;
            auto& nowq = qu[edges[e].w];
            if(nowq.empty() || nowq.back().id != i)nowq.push_back({i, {}});
            nowq.back().q_edges.push_back(e);
        }
    }

    for(int i=1;i<=maxw;i++){
        for(auto [u,v]:ev[i-1])dsu.unite(u,v);
        for(const auto& [id,q_edges]:qu[i]){
            int S = dsu.S();
            for(auto e:q_edges){
                auto [u,v,_] = edges[e];
                if(dsu.find(u) == dsu.find(v)){
                    ans[id]=0;break;
                }
                dsu.unite(u,v);
            }
            dsu.rev(S);
        }
    }

    for(int i=1;i<=q;i++){
        if(ans[i])YES;
        else NO;
    }

    return 0;
}

Kruskal 重构树

构建方式

先构建 $n$ 个集合和 $n$ 个点权为 $0$ 的点，每个集合都有一个代表节点。

对于一颗最小生成树，按边权从小到大排序，对于每一条边 $(u,v,w)$ ，构建一个新的点权为 $w$ 的节点，作为集合 $u,v$ 代表节点的父亲，并将集合 $u,v$ 合并，代表节点更新为新节点。

这样我们就得到了一颗有 $2n-1$ 个节点， $n$ 个叶子的二叉树，这棵树就被称作 Kruskal 重构树。

性质

在 Kruskal 重构树上，任意两个叶子节点的 LCA 的点权就是在原图上这两个节点之间所有路径最大边权的最小值。

由此我们看也可以得出，在原图上从节点 $u$ 出发经过所有边权 $\le w$ 的边能到达的节点，就是在 Kruskal 重构树上 $u$ 深度最小且点权 $\le w$ 的祖先 $v$ 的子树中所有叶子节点。

例题

P4768 [NOI2018] 归程

对于水位线的限制我们已经知道了是在 Kruskal 重构树上的某一个子树，只需要求出子树中所有叶子节点到 $1$ 的最短路的最小值即可。先预处理出来最短路，然后在构建 Kruskal 重构树时维护这个最小值。

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
inline int read(){int f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}

const int N = 4e5+5;

int n,m;
vector<pair<int,int>> G[N];
bool vis[N];
ll dis[N];
vector<int> tree[N+N];
vector<tuple<int,int,int>> edges;
int fa[N*2],val[N*2];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int i,int j){fa[find(i)]=find(j);}

ll mindis[N*2];
int zx[N*2][20],dep[N*2];
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    zx[u][0]=f;
    for(int i=1;i<=__lg(dep[u]);i++){
        zx[u][i]=zx[zx[u][i-1]][i-1];
    }

    if(u<=n){
        mindis[u]=dis[u];
        return;
    }

    mindis[u]=LONG_LONG_MAX;
    for(int v:tree[u]){
        if(v==f)continue;
        dfs(v,u);

        mindis[u]=min(mindis[u],mindis[v]);
    }
}

void solve(){
    edges.clear();
    memset(fa,0,sizeof(fa));
    memset(val,0,sizeof(val));
    memset(zx,0,sizeof(zx));
    memset(dep,0,sizeof(dep));
    memset(mindis,0,sizeof(mindis));

    n=read(),m=read();
    for(int i=1;i<=n;i++)G[i].clear();
    for(int i=1;i<=n+m;i++)tree[i].clear();

    for(int i=0;i<m;i++){
        int u=read(),v=read(),l=read(),a=read();
        G[u].push_back({v,l});
        G[v].push_back({u,l});
        edges.push_back({-a,u,v});
    }

    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,1});

    while(pq.size()){
        auto u=pq.top().second;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        
        for(auto [v,w]:G[u]){
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                pq.push({-dis[v],v});
            }
        }
    }

    sort(edges.begin(), edges.end());
    int cnt = n;
    for(int i=1;i<=n*2;i++){
        fa[i]=i,val[i]=i;
    }

    for(auto [a,u,v]:edges){
        int fu=find(u),fv=find(v);
        if(fu!=fv){
            ++cnt;
            tree[fu].push_back(cnt);tree[cnt].push_back(fu);
            tree[fv].push_back(cnt);tree[cnt].push_back(fv);
            fa[fu]=fa[fv]=cnt;
            val[cnt]=-a;
        }
    }

    dfs(cnt, 0);

    int q=read(),k=read(),s=read();
    ll lastans = 0;

    while(q--){
        int v = ((ll)read()+k*lastans-1)%n+1;
        int p = (read()+k*lastans)%(s+1);
    
        for(int i=__lg(dep[v]);i>=0;i--){
            if(val[zx[v][i]]>p)v=zx[v][i];
        }

        printf("%lld\n",mindis[v]);

        lastans = mindis[v];
    }
}


int main(){
    int T=read();
    while(T--)solve();
    return 0;
}