Problem: The students in a class in Akabe high-school define the relation “acquaintance” as:

* If A and B are friends, then A is acquainted with B.
* If A and B are friends and B is acquainted with C, then A is acquainted with C.



They define the relation “companion” as:

* Suppose A is acquainted with B, and two classmates who have been friend distance. If A is still acquainted with B, then A and B are companions.



A boy PCK joined the class recently and wishes to hold a party inviting his class fellows. He wishes to invite as many boys and girls as possible to the party and has written up an invitation list. In arranging the list, he placed the following conditions based on the acquaintanceship within the class before he joined.

When T is in the list:

* U is listed if he/she is a companion of T.
* If U is not a companion of T, U is not listed if he/she and T are friends, or he/she and some of T’s companions are friends.



PCK made the invitation list so that the maximum number of his classmates is included.

Given the number of classmates N and the friendships among them, write a program to estimate the number of boys and girls in the list. All the classmates are identified by an index that ranges from 0 to N-1.



Input

The input is given in the following format.


N M
s_1 t_1
s_2 t_2
:
s_M t_M


The first line provides the number of classmates N (2 ≤ N ≤ 105) and the number of friendships M (1 ≤ M ≤ 2×105). Each of the M subsequent lines provides two of the classmates s_i, t_i (0 ≤ s_i,t_i ≤ N-1) indicating they are friends. No duplicate relationship appears among these lines.

Output

Output the maximum number of classmates PCK invited to the party.

Examples

Input

7 8
0 1
1 2
1 3
2 3
0 4
4 5
4 6
5 6


Output

6


Input

3 2
0 1
1 2


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100001

struct Edge{
	int from,to;
	bool is_bridge;
};

struct Info{
	Info(int arg_to,int arg_edge_index){
		to = arg_to;
		edge_index = arg_edge_index;
	}
	int to,edge_index;
};

struct Node{
	int parent,value,self_yes_num,self_no_num;
	vector<int> children;
};

int N,E;
int number;
int node_index,treeTop_index;
int height[NUM],boss[NUM],member_num[NUM],node_rabel[NUM],boss_node[NUM];
int order[NUM],lowlink[NUM];
int treeTop[NUM];
bool visited[200000],rabel_check[NUM],tree_used[NUM];
Edge edge[200005];
vector<Info> first_G[NUM];
vector<int> G[NUM];
Node nodes[NUM];

int get_boss(int id){
	if(id == boss[id])return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

void unite(int x,int y){

	int x_boss_id = get_boss(x);
	int y_boss_id = get_boss(y);

	if(x_boss_id == y_boss_id)return;

	if(height[x_boss_id] < height[y_boss_id]){
		boss[x_boss_id] = y_boss_id;
		member_num[y_boss_id] += member_num[x_boss_id];
	}else{
		boss[y_boss_id] = x_boss_id;
		member_num[x_boss_id] += member_num[y_boss_id];
		if(height[x_boss_id] == height[y_boss_id])height[x_boss_id]++;
	}
}

void recursive(int node_id){

	order[node_id] = number++;
	lowlink[node_id] = order[node_id];

	int next_node;

	for(int i = 0; i < first_G[node_id].size(); i++){

		next_node = first_G[node_id][i].to;

		if(order[next_node] == -1){ //未訪問

			visited[first_G[node_id][i].edge_index] = true;
			recursive(next_node);
			lowlink[node_id] = min(lowlink[node_id],lowlink[next_node]); //葉方向のmin

		}else if(visited[first_G[node_id][i].edge_index] == false){ //後退辺(訪問済ノードに向かう辺)

			lowlink[node_id] = min(lowlink[node_id],order[next_node]);
		}
	}
}

void makeTree(int node_id,int pre_node){

	tree_used[node_id] = true;
	if(pre_node != -1){
		nodes[node_id].parent = pre_node;
		nodes[pre_node].children.push_back(node_id);
	}

	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] == pre_node)continue;
		makeTree(G[node_id][i],node_id);
	}
}

void calc(int node_id){

	nodes[node_id].self_yes_num = nodes[node_id].value; //自分を含む場合の数
	nodes[node_id].self_no_num = 0;

	//子を先に計算する
	for(int i = 0; i < nodes[node_id].children.size(); i++){
		calc(nodes[node_id].children[i]);
	}

	//自分を含む場合、含まない場合を計算
	int child_id;
	for(int i = 0; i < nodes[node_id].children.size(); i++){
		child_id = nodes[node_id].children[i];
		nodes[node_id].self_yes_num += nodes[child_id].self_no_num; //自分がyesなら子供はno
		nodes[node_id].self_no_num += max(nodes[child_id].self_yes_num,nodes[child_id].self_no_num); //自分がnoなら、子はyes,noどちらでも良い
	}
}


int main(){

	scanf("%d %d",&N,&E);

	for(int i = 0; i < E; i++){
		scanf("%d %d",&edge[i].from,&edge[i].to);
		edge[i].is_bridge = false;
		first_G[edge[i].from].push_back(Info(edge[i].to,i));
		first_G[edge[i].to].push_back(Info(edge[i].from,i));
	}

	//橋を検出する
	for(int i = 0; i < N; i++){
		order[i] = -1;
		lowlink[i] = -1;
	}

	for(int i = 0; i < E; i++){
		visited[i] = false;
	}

	//★グラフは連結とは限らない★
	for(int i = 0; i < N; i++){
		if(order[i] == -1){
			number = 0;
			recursive(i);
		}
	}

	int from,to;
	for(int i = 0; i < E; i++){

		from = edge[i].from;
		to = edge[i].to;

		if(order[from] > order[to]){
			swap(from,to);
		}

		if(order[from] < lowlink[to]){ //toへ到達するには、必ず辺iを通過しなければならない
			edge[i].is_bridge = true;
		}
	}

	//二重辺連結成分をuniteする
	for(int i = 0; i < N; i++){
		boss[i] = i;
		height[i] = 0;
		member_num[i] = 1;
	}

	for(int i = 0; i < E; i++){
		if(edge[i].is_bridge)continue;
		unite(edge[i].from,edge[i].to);
	}

	//uniteした二重辺連結成分をノードにまとめる
	int boss_id;
	node_index = 0;
	for(int i = 0; i < N; i++)rabel_check[i] = false;

	//グループにノード番号を付与
	for(int i = 0; i < N; i++){
		boss_id = get_boss(i);
		if(!rabel_check[boss_id]){ //初登場
			node_rabel[node_index] = boss_id;
			boss_node[boss_id] = node_index;
			nodes[node_index].value = member_num[boss_id];
			node_index++;
			rabel_check[boss_id] = true;
		}
	}

	//ノードの辺を設定する(★橋のみが辺となる:仮に閉路があれば、橋は橋として検出されないので、木ができる★)
	int from_boss_id,to_boss_id;
	for(int i = 0; i < E; i++){
		if(!edge[i].is_bridge)continue;

		from_boss_id = get_boss(edge[i].from);
		to_boss_id = get_boss(edge[i].to);
		G[boss_node[from_boss_id]].push_back(boss_node[to_boss_id]);
		G[boss_node[to_boss_id]].push_back(boss_node[from_boss_id]);
	}

	//ノードを木構造にする(★複数の木ができる可能性あり★)
	for(int i = 0; i < node_index; i++)tree_used[i] = false;

	treeTop_index = 0;
	for(int i = 0; i < node_index; i++){
		if(tree_used[i])continue;

		treeTop[treeTop_index++] = i;
		makeTree(i,-1);
	}

	int ans = 0;

	//木構造で最大独立重み集合を求める
	for(int i = 0; i < treeTop_index; i++){
		calc(treeTop[i]);
		ans += max(nodes[treeTop[i]].self_yes_num,nodes[treeTop[i]].self_no_num);
	}

	printf("%d\n",ans);

	return 0;
}