给定一个包含 n 个顶点和 m 条边的无向图。顶点编号为 1 到 n 。图中没有自环或重边。

你的任务是通过为每条边选择一个方向，将图变为有向图。定向之后，定义一个顶点序列 v1​,v2​,…,vk​ （其中 k 可以任意大，任何顶点可以重复任意次数）为交替路径，如果：

• 边 (v1​,v2​) 从 v1​ 指向 v2​
  
• 边 (v2​,v3​) 从 v3​ 指向 v2​
  
• 边 (v3​,v4​) 从 v3​ 指向 v4​
  
• 边 (v4​,v5​) 从 v5​ 指向 v4​
  
• 以此类推……
  

即边的方向交替为：→, ←, →, ←, …

如果一个顶点 v 满足：原图中从 v 出发的任意路径（不一定是简单路径）在定向后的有向图中都是交替路径，则称 v 为美丽顶点。

求：在定向边之后，最多能使多少个顶点成为美丽顶点？

代码

// Sunshine, sunshine, ladybugs awake!
// Clap your hooves and do a little shake!
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

using PII=pair<int,int> ;
//inline static constexpr int MAXN=100010;

const int MAXN=200010;
vector<int> adj[MAXN];

void solve() {
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)adj[i].clear();
	
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	vector<int> f(n+1,-1);
	int ans=0;
	
	for(int i=1;i<=n;i++){
		if(f[i]!=-1) continue;
		
		queue<int> q;
		q.push(i);
		f[i]=0;
		
		int cnt[2]={1,0};
		bool flag=true;
		
		while(!q.empty()){
			int u=q.front();
			q.pop();
			
			for(auto v:adj[u]){
				if(f[v]==-1){
					f[v]=1^f[u];
					cnt[f[v]]++;
					q.push(v);
				}else if(f[v]==f[u]){
					flag=false;
				}
			}
		}
		if(flag){
			ans+=max(cnt[0],cnt[1]);
		}
	}
	cout<<ans<<endl;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;cin >> t;while (t--) 
		solve();
	return 0;
}