//郑老师和na姐一样可爱^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define db double
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
vector<int>g[500010];
int n,m,depth[500010],fa[500010][21],dp[500010],ans;
void bfs(int x){
    memset(depth,0x3f3f,sizeof depth);
    queue<int>q;q.push(x);
    depth[0]=0,depth[x]=1;
    while(q.size()){
        auto u=q.front();q.pop();
        for(auto v:g[u]){
            if(depth[v]>depth[u]+1){
                depth[v]=depth[u]+1;
                q.push(v);
                fa[v][0]=u;
                for(int k=1;k<=19;k++)fa[v][k]=fa[fa[v][k-1]][k-1];
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a]>depth[b])swap(a,b);
    for(int k=19;k>=0;k--)if(depth[fa[b][k]]>=depth[a])b=fa[b][k];
    if(a==b)return a;
    for(int k=19;k>=0;k--){
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int dis(int a, int b){
    int c = lca(a, b);
    return abs(depth[c]-depth[a]) + abs(depth[c]-depth[b]);
}
void dfs(int u){
    for(auto v:g[u]){
        if(depth[v]<depth[u])continue;
        dfs(v);
        dp[u]+=dp[v];
        if(!dp[v])ans+=m;
        else if(dp[v]==1)ans++;
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1);
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        int f=lca(u,v);
        dp[f]-=2;
        dp[u]++,dp[v]++;
    }
    dfs(1);
    cout<<ans<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t；
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//Ö£ÀÏʦºÍna½ãÒ»Ñù¿É°®^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b) {return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define db double
#define mk make_pair
#define pi acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m,p[100010],fa[100010][17],d1[100010][17],d2[100010][17],depth[100010];
vector<PII>g[100010];
int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
void dfs(int x){
    queue<int>q;q.push(x);
    memset(depth,0x3f3f,sizeof depth);
    depth[0]=0,depth[x]=1;
    while(q.size()){
        auto u=q.front();q.pop();
        for(auto [v,w]:g[u]){
            if(depth[v]>depth[u]+1){
                depth[v]=depth[u]+1;
                q.push(v);
                fa[v][0]=u;
                int dist1=w,dist2=-INF;
                d1[v][0]=w,d2[v][0]=-INF;
                for(int i=1;i<=16;i++){
                    int anc=fa[v][i-1];
                    fa[v][i]=fa[anc][i-1];
                    int d[4]={d1[v][i-1],d2[v][i-1],d1[anc][i-1],d2[anc][i-1]};
                    for(int j=0;j<4;j++){
                        if(dist1<d[j])dist2=dist1,dist1=d[j];
                        else if(dist1!=d[j]&&dist2<d[j])dist2=d[j];
                    }
                    d1[v][i]=dist1;
                    d2[v][i]=dist2;
                }
            }
        }
    }
}
int lca(int a,int b,int w){
    static int d[200010];
    int cnt=0;
    if(depth[a]>depth[b])swap(a,b);
    for(int i=16;i>=0;i--){
        if(depth[fa[b][i]]>=depth[a]){
            d[cnt++]=d1[b][i];
            d[cnt++]=d2[b][i];
            b=fa[b][i];
        }
    }
    if(a!=b){
        for(int i=16;i>=0;i--){
            if(fa[a][i]!=fa[b][i]){
                d[cnt++]=d1[a][i];
                d[cnt++]=d2[a][i];
                d[cnt++]=d1[b][i];
                d[cnt++]=d2[b][i];
                a=fa[a][i];
                b=fa[b][i];
            }
        }
    }
    d[cnt++]=d1[a][0];
    d[cnt++]=d2[a][0];
    int dist1=-INF/2,dist2=-INF;
    for(int i=0;i<cnt;i++){
        if(d[i]>dist1)dist2=dist1,dist1=d[i];
        else if(dist1!=d[i]&&d[i]>dist2)dist2=d[i];
    }
    if(w==dist1)return -dist2+w;
    else return -dist1+w;
}
void solve(){
    cin>>n>>m;
    vector<tuple<int,int,int,bool>>v;
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        if(a!=b)v.push_back({c,a,b,0});
    }
    sort(all(v));
    for(int i=1;i<=n;i++)p[i]=i;
    int res=0;
    for(int i=0;i<v.size();i++){
        auto &[w,a,b,f]=v[i];
        int pa=find(a),pb=find(b);
        if(pa!=pb){
            p[pa]=pb;
            f=1;
            res+=w;
        }
    }
    for(int i=0;i<v.size();i++){
        auto [w,a,b,f]=v[i];
        if(f){
            g[a].push_back({b,w});
            g[b].push_back({a,w});
        }
    }
    dfs(1);
    int ans=INF;
    for(int i=0;i<v.size();i++){
        auto [w,a,b,f]=v[i];
        if(!f)ans=min(ans,res+lca(a,b,w));
    }
    cout<<ans<<endl;
}
signed main() {
    fast
    int t=1;//cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

//郑老师和阿梓一样可爱^_^
//r[i]表示我们需要的人数i时刻 num[i]表示i时刻我们有的人数 x[i]表示我们i时刻选择的人数
//0<=x[i]<=num[i]
//x[i-7]+x[i-6]+...+x[i]>=r[i] 
//前缀和一下
//s[i]-s[i-8]>=r[i] 切记连边是左边去连右边
//要体现s[24]=s24 就必须要 s[24]>=c s[24]<=c 给0连起来就可以了
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int r[25],n,num[25],dist[25],cnt[25],st[25];
vector<PII>g[25];
bool spfa(int s24){
    queue<int>q;
    q.push(24);
    memset(dist,-0x3f3f,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    dist[24]=s24;
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=1;
        for(auto [v,w]:g[u]){
            if(dist[v]<dist[u]+w){
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=25)return true;
                q.push(v);
                st[v]=0;
            }
        }
    }
    return false;
}
void solve(){
    for(int i=0;i<=24;i++){
        st[i]=cnt[i]=num[i]=0;
    }
    for(int i=1;i<=24;i++)cin>>r[i];
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;cin >> x;x++;
        num[x]++;
    }
    for(int s24=0;s24<=1000;s24++){
        for(int i=0;i<=24;i++){
            g[i].clear();
        }
        for(int i=1;i<=24;i++){
            g[i-1].push_back({i,0});
            g[i].push_back({i-1,-num[i]});
            if(i>=8)g[i-8].push_back({i,r[i]});
            else g[i+16].push_back({i,r[i]-s24});
        }
        g[24].push_back({0,-s24});
        g[0].push_back({24,s24});
        if(!spfa(s24)){
            cout<<s24<<endl;
            return;
        }
    }
    cout<<"No Solution"<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

// max -> 最短路
// 奶牛排在队伍中的顺序和它们的编号是相同的。 x[i]<=x[i+1] i+1->i w=0
// x[b]-x[a]<=L x[b]<=x[a]+L a->b w=L
// x[b]-x[a]>=D x[a]<=x[b]-D b->a w=-D
//判-1就是check 负环 全部放进去跑一遍即可
//判-2就是看他跑完最短路之后dist[n]
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,dist[10010],st[10010],cnt[10010];
vector<pair<int,int>>g[10010];
bool spfa(int x){
    queue<int>q;
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++)cnt[i]=st[i]=0;
    for(int i=1;i<=x;i++){
        q.push(i);
        dist[i]=0;
    }
    while(q.size()){
        auto u=q.front();q.pop();
        //cout<<dist[u]<<' '<<u<<endl;
        if(st[u])continue;
        st[u]=1;
        for(auto [v,w]:g[u]){
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)return true;
                q.push(v);
                st[v]=0;
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m1>>m2;
    for(int i=1;i<n;i++){
        g[i+1].push_back({i,0});
    }
    while(m1--){
        int a,b,w;cin>>a>>b>>w;
        g[a].push_back({b,w});
    }
    while(m2--){
        int a,b,w;cin>>a>>b>>w;
        g[b].push_back({a,-w});
    }
    if(spfa(n)){
        cout<<-1<<endl;
        return 0;
    }
    spfa(1);
    if(dist[n]!=0x3f3f3f3f)cout<<dist[n]<<endl;
    else cout<<-2<<endl;
    return 0;
}

建出trie之后
考虑从根节点往下贪心考虑（高位到低位）
考虑节点要是分叉的情况我们序列中必然有数该位上为1
这样我们需要考虑往左往右走才是更优的
要是我们往左走了 就相当于可以不考虑右边的子树了 因为他们那边连高位的‘1’都没有显然不可能是最大值
要是不分叉我们就直接走就是了
然后考虑dp[u]:表示节点u子树包括的数异或后（ans）的最小值是什么
转移自然就只有三种 分叉一种 不分叉两种
分叉的话显然是左右两边的最小值+现在该位必为‘1’ dp[u]=min(dp[l],dp[r])+1<<(该位)
不分叉直接dp[u]=dp[]即可

C++ 代码

//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
using namespace std;
int n,idx,son[3000010][2],a[100010],dp[3000010];
void add(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
}
void dfs(int p,int now){
    int l=son[p][0],r=son[p][1];
    if(l)dfs(l,now-1);
    if(r)dfs(r,now-1);
    if(l&&!r)dp[p]+=dp[l];
    else if(r&&!l)dp[p]+=dp[r];
    else if(r&&l)dp[p]=min(dp[l],dp[r])+(1<<now);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(a[i]);
    }
    dfs(0,30);
    cout<<dp[0]<<endl;
    return 0;
}

//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,dist[500010];
vector<PII>g[500010];
bool st[500010];
void spfa(){
    queue<int>q;
    q.push(0);
    memset(dist,-0x3f3f,sizeof dist);
    dist[0]=0;
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto [v,w]:g[u]){
            if(dist[v]<dist[u]+w){
                dist[v]=dist[u]+w;
                q.push(v);
                st[v]=false;
            }
        }
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b,w;cin>>a>>b>>w;
        a++,b++;
        g[a-1].push_back({b,w});
    }
    for(int i=1;i<500010;i++){
        g[i-1].push_back({i,0});
        g[i].push_back({i-1,-1});
    }
    spfa();
    cout<<dist[500001]<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
//#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,m,cnt[100010],q[100010],h[N],e[3*N],w[3*N],ne[3*N], idx;
long long dist[100010];
bool st[100010];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(){
    int hh = 0, tt = 1;
    q[0]=0;
    memset(dist,-0x3f,sizeof dist);
    dist[0]=0;
    st[0]=true;
    while(hh!=tt){
        auto t=q[--tt];
        st[t]=false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
void solve(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    for(int i=1;i<=m;i++){
        int x,a,b;cin>>x>>a>>b;
        if (x == 1) add(b, a, 0), add(a, b, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    for(int i=1;i<=n;i++)add(0,i,1);
    if(spfa())cout<<-1<<endl;
    else{
        long long ans=0;
        for(int i=1;i<=n;i++){
            ans+=dist[i];
        }
        cout<<ans<<endl;
    }
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
//优化：优化点数 只看两个字符最多就是26*26个点
//时间复杂度大概是1e8但是过不了呢
//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

using namespace std;
const int mod = 998244353;
const int N = 5e5 + 10;
//const int M = 998244353;
//#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n;
vector<pair<int,db>>g[1010];
bool check(db mid){ //676*10000*log
    queue<int>q;
    for(int i=0;i<=676;i++)if(g[i].size())q.push(i);
    vector<int>cnt(1010),st(1010);
    vector<db>dist(1010);
    int count=0;
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=1;
        for(auto [v,W]:g[u]){
            db c=mid-W;
            if(dist[v]>dist[u]+c){
                dist[v]=dist[u]+c;
                cnt[v]=cnt[u]+1;
                if(++count>=10000)return true;
                if(cnt[v]>=676){
                    //cout<<"true:"<<mid<<endl;
                    return true;
                }
                q.push(v);
                st[v]=0;
            }
        }
    }
    //cout<<"false:"<<mid<<endl;
    return false;
}
void solve(){
    while(cin>>n,n){
        for(int i=0;i<=676;i++){
            g[i].clear();
        }
        for(int i=1;i<=n;i++){
            string s;cin>>s;
            if(s.size()<2)continue;
            int v=(s[0]-'a')*26+(s[1]-'a'),u=(s[s.size()-2]-'a')*26+s.back()-'a';
            //cout<<u<<' '<<v<<' '<<s.size()<<endl;
            g[u].push_back({v,s.size()});
        }
        db l=0,r=1000;
        if(!check(0)){
            cout<<"No solution"<<endl;
            continue;
        }
        while(r-l>=1e-4){
            db mid=(l+r)/2;
            if(check(mid))l=mid;
            else r=mid;
        }
        printf("%.2f\n",l);
    }
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,m;
db w[1010];
vector<pair<int,db>>G[1010];
bool check(db mid){
    vector<pair<int,db>>g[n+1];
    for(int u=1;u<=n;u++){
        for(auto [v,W]:G[u]){
            db c=mid*(db)W-(db)w[u];
            g[u].push_back({v,c});
        }
    }
    queue<int>q;
    vector<int>st(n+1),cnt(n+1);
    vector<db>dist(n+1);
    for(int i=1;i<=n;i++)q.push(i);
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=1;
        for(auto [v,W]:g[u]){
            if(dist[v]>dist[u]+W){
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)return true;
                dist[v]=dist[u]+W;
                q.push(v);
                st[v]=0;
            }
        }
    }
    return false;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    db l=0,r=1000;
    while(r-l>=1e-4){
        db mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

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

void solve(){
    int n,m1,m2;cin>>n>>m1>>m2;
    vector<pair<int,int>>g[n+1];
    while(m1--){
        int a,b,w;cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    while(m2--){
        int a,b,w;cin>>a>>b>>w;
        g[a].push_back({b,-w});
    }
    queue<int>q;
    vector<int>dist(n+1),st(n+1),cnt(n+1);
    for(int i=1;i<=n;i++)q.push(i);
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=1;
        for(auto [v,w]:g[u]){
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n){
                    cout<<"YES"<<endl;
                    return;
                }
                q.push(v);
                st[v]=0;
            }
        }
    }
    cout<<"NO"<<endl;
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}