Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N. The edges in this graph are represented by (u_i, v_i). There are no self-loops and multiple edges in this graph.

Based on this graph, Takahashi is now constructing a new graph with N^2 vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq a \leq N, 1 \leq b \leq N). The edges in this new graph are generated by the following rule:

* Span an edge between vertices (a, b) and (a', b') if and only if both of the following two edges exist in the original graph: an edge between vertices a and a', and an edge between vertices b and b'.



How many connected components are there in this new graph?

Constraints

* 2 \leq N \leq 100,000
* 0 \leq M \leq 200,000
* 1 \leq u_i < v_i \leq N
* There exists no pair of distinct integers i and j such that u_i = u_j and v_i = v_j.

Input

The input is given from Standard Input in the following format:


N M
u_1 v_1
u_2 v_2
:
u_M v_M


Output

Print the number of the connected components in the graph constructed by Takahashi.

Examples

Input

3 1
1 2


Output

7


Input

7 5
1 2
3 4
3 5
4 5
2 6


Output

18
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

vector<int>E[200000];
int id[200000];
int d[200000];

void dfs(int v,int k){
	id[v]=k;
	for(int u:E[v]){
		if(id[u]==-1){
			if(d[v]!=-1)d[u]=!d[v];
			dfs(u,k);
		}
		else{
			if(d[u]==d[v]){
				d[u]=-1;
			}
		}
	}
}
vector<int>v[200000];

int main(){
	int n,m;cin>>n>>m;
	rep(i,m){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	memset(id,-1,sizeof(id));
	int cnt=0;
	rep(i,n){
		if(id[i]==-1){
			dfs(i,cnt++);
		}
		v[id[i]].push_back(i);
	}
	ll c1=0,c2=0,c3=0;
	rep(i,cnt){
		if(v[i].size()==1){
			c1++;
			continue;
		}
		c2++;
		bool flag=true;
		for(int j:v[i]){
			if(d[j]==-1)flag=false;
		}
		if(flag)c3++;
	}
	cout<<c1*(n-c1)*2+c1*c1+c2*c2+c3*c3<<endl;
}