$10^5$，非常稀疏的图，可以尝试 Dinic 网络流。

因为每条边都要被线路覆盖一次，所以考虑上下界网络流建边下界为 $1$，上界为无限大。

然后因为线路可以从任意点开始和结束，于是考虑建超级源点和汇点，超级源点向每个点，每个点向超级汇点都连一条下界为 $0$，上界为无限大的边。

直接跑上下界最小流就做完了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t,S,T;
int head[100010],to[1000010],nxt[1000010],val[1000010],tot=1;
void add(int u,int v,int w){
	to[++tot]=v,val[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
}
int maxflow,dis[100010],now[100010];
bool vis[100010];
bool bfs(){
	queue<int>q;
	memset(vis,0,sizeof vis);
	vis[s]=1,dis[s]=0,now[s]=head[s];
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=nxt[i]){
			if(vis[to[i]] || !val[i]) continue;
			now[to[i]]=head[to[i]];
			dis[to[i]]=dis[u]+1,vis[to[i]]=1;
			q.push(to[i]);
			if(to[i]==t) return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t) return flow;
	int rest=flow;
	for(int i=now[x];i && rest;i=nxt[i]){
		now[x]=i;
		if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
		int v=dinic(to[i],min(rest,val[i]));
		if(!v) dis[to[i]]=0;
		val[i]-=v,val[i^1]+=v;
		rest-=v;
	}
	return flow-rest;
}
int V[100010],_val[1000010];
signed main() {
	cin>>n;
	S=0,T=n+1; 
	s=n+2,t=n+3;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u++,v++;
		add(u,v,1e16-1),add(v,u,0);
		V[v]++,V[u]--;
	}
	for(int i=1;i<=n;i++) add(S,i,1e16),add(i,S,0),add(i,T,1e16),add(T,i,0);
	int sum=0;
	for(int i=0;i<=n+1;i++) if(V[i]>0) add(s,i,V[i]),add(i,s,V[i]),sum+=V[i];else if(V[i]<0) add(i,t,-V[i]),add(t,i,-V[i]);
	add(T,S,1e15),add(S,T,0);
	int flow=0;
	while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
	if(maxflow<sum) cout<<"A clever xzy~~~";
	else{
		for(int i=1;i<=tot;i++) _val[i]=val[i];
		s=T,t=S;
		int ans=val[tot];
		val[tot]=val[tot^1]=0;
		maxflow=0;
		while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
		cout<<ans-maxflow<<" ";
	}
	return 0;
}