stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<queue>

#include<stack>

using namespace std;

int main()

{

	int n,x[100005],y[100005],t[100005],flag=1;

	cin >> n;

	for(int i=1;i<=n;i++)

	{

		cin >> t[i] >> x[i] >> y[i];

		if(t[i]<x[i]+y[i])

			flag=0;

		else

		{

			if((x[i]+y[i])%2==0&&t[i]%2!=0)

				flag=0;

			else if((x[i]+y[i])%2!=0&&t[i]%2==0)

				flag=0;

		}

		

	}

		if(flag)

			cout << "Yes";

		else

			cout << "No";

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    long N,x[100005],y[100005],t[100005],z;

	while(scanf("%ld",&N)!=EOF)

	{

		int flag=0;

		for(int i=0;i<N;i++)

			scanf("%ld%ld%ld",&t[i],&x[i],&y[i]);

		for(int i=0;i<N;i++)

		{

			z=t[i]-x[i]-y[i];

			if(t[i]<x[i]+y[i])

			{

				printf("No\n");

				flag=1;

				break;

			}

			else if(z%2!=0)

			{

				printf("No\n");

				flag=1;

				break;

			}			

		}

		if(flag==0)

		printf("Yes\n");

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <map>

#include <set>

#include <queue>

#include <stack>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;



#define ls st<<1

#define rs st<<1|1

#define CLR(a,b) memset(a,(b),sizeof(a))



const int MAXN = 1e5+11;

const int mod = 1e9+7;

const int INF = 0x3f3f3f3f;



/*-------------------------------------------------------*/

int abc(int x)

{

    if(x < 0) return -x;

    return x;

}

int x[MAXN], y[MAXN], t[MAXN];

int main() {

    int n;

    scanf("%d",&n);

    for(int i = 1; i <= n; i++) {

        scanf("%d%d%d",&t[i],&x[i],&y[i]);

    }

    x[0] = 0, y[0] = 0, t[0] = 0;

    bool flag = true;

    for(int i = 1; i <= n; i++) {

        int tt = (t[i] - t[i-1]);

        int st = abc(x[i]-x[i-1])+abc(y[i]-y[i-1]);

        if(tt<st || st%2 !=tt%2) {

          flag = false; break;

        }



        }

        //if(t[i]==(x[i]-x[i-1]+y[i]-y[i+1]) continue;

    if(flag) printf("Yes\n");

    else printf("No\n");

return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    long N,x[100005],y[100005],t[100005],z;

	while(scanf("%ld",&N)!=EOF)

	{

		int flag=0;

		for(int i=0;i<N;i++)

			scanf("%ld%ld%ld",&t[i],&x[i],&y[i]);

		for(int i=0;i<N;i++)

		{

			z=t[i]-x[i]-y[i];

			if(t[i]<x[i]+y[i])

			{

				printf("No\n");

				flag=1;

				break;

			}

			else if(z%2!=0)

			{

				printf("No\n");

				flag=1;

				break;

			}			

		}

		if(flag==0)

		printf("Yes\n");

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int n;

	while(~scanf("%d",&n)){

		int flag=0;

		while(n--){

			int t,x,y;

			scanf("%d%d%d",&t,&x,&y);

			if((t-(x+y))%2||t<(x+y)){

				flag=1;

			}

		}

		if(flag){

			printf("No\n");

		}else{

			printf("Yes\n");

		}

		

		

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    long N,x[100005],y[100005],t[100005],z;

	while(scanf("%ld",&N)!=EOF)

	{

		int flag=0;

		for(int i=0;i<N;i++)

			scanf("%ld%ld%ld",&t[i],&x[i],&y[i]);

		for(int i=0;i<N;i++)

		{

			z=t[i]-x[i]-y[i];

			if(t[i]<x[i]+y[i])

			{

				printf("No\n");

				flag=1;

				break;

			}

			else if(z%2!=0)

			{

				printf("No\n");

				flag=1;

				break;

			}			

		}

		if(flag==0)

		printf("Yes\n");

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct Node

{

	int t,x,y;

}p[100010];

bool cmp(Node a,Node b)

{

	return a.t <b.t ;

}

int main()

{

	int n;

	while(scanf("%d",&n)!=EOF)

	{

		int f=1;

		memset(p,0,sizeof(p));

		for(int i = 1; i <= n; i++)

		{

			scanf("%d%d%d",&p[i].t ,&p[i].x,&p[i].y);

		}

		sort(p+1,p+n+1,cmp);

		for(int i = 1; i <= n; i++)

		{

			int ans=(p[i].x+p[i].y)-(p[i-1].x+p[i-1].y);

			if((p[i].t-p[i-1].t-ans)%2!=0||(p[i].t-p[i-1].t)<ans)

			f=0;

		}

		if(f)

		printf("Yes\n");

		else

		printf("No\n");

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    long N,x[100005],y[100005],t[100005],z;

	while(scanf("%ld",&N)!=EOF)

	{

		int flag=0;

		for(int i=0;i<N;i++)

			scanf("%ld%ld%ld",&t[i],&x[i],&y[i]);

		for(int i=0;i<N;i++)

		{

			z=t[i]-x[i]-y[i];

			if(t[i]<x[i]+y[i])

			{

				printf("No\n");

				flag=1;

				break;

			}

			else if(z%2!=0)

			{

				printf("No\n");

				flag=1;

				break;

			}			

		}

		if(flag==0)

		printf("Yes\n");

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

using namespace std;



int main(){

    long N;

    cin >> N;

    long t[100010]={}, x[100010]={}, y[100010]={};

    for(long i=1; i<=N; i++){

        cin >> t[i] >> x[i] >> y[i];

    }

    

    long dt=0, distance=0;

    bool frag=true;

    

    for(long i=0; i<N; i++){

        dt=t[i+1]-t[i];

        distance=abs(x[i+1]-x[i])+abs(y[i+1]-y[i]);

        if(dt<distance){

            frag=false;

            break;

        }

        if((dt-distance)%2==0){

            frag=true;

            continue;

        }else{

            frag=false;

            break;

        }

    }

    

    if(frag==true){

        cout << "Yes" << endl;

    }else{

        cout << "No" << endl;

    }

    

    return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

#include<math.h>

using namespace std;



int main(){

    int N;

    cin >> N;

    vector<int> t(N+1, 0), x(N+1, 0), y(N+1, 0);

    for(int i=1; i<=N; i++){

        cin >> t.at(i) >> x.at(i) >> y.at(i);

    }

    

    int dt=0, distance=0;

    bool frag=true;

    

    for(int i=0; i<N; i++){

        dt=t.at(i+1)-t.at(i);

        distance=abs(x.at(i+1)-x.at(i))+abs(y.at(i+1)-y.at(i));

        if(dt<distance){

            frag=false;

            break;

        }

        if((dt-distance)%2==0){

            frag=true;

            continue;

        }else{

            frag=false;

            break;

        }

    }

    

    if(frag==true){

        cout << "Yes" << endl;

    }else{

        cout << "No" << endl;

    }

    

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

using namespace std;



int main(){

    int N;

    cin >> N;

    int t[100010]={}, x[100010]={}, y[100010]={};

    for(int i=1; i<=N; i++){

        cin >> t[i] >> x[i] >> y[i];

    }

    

    int dt=0, distance=0;

    bool frag=true;

    

    for(int i=0; i<N; i++){

        dt=t[i+1]-t[i];

        distance=abs(x[i+1]-x[i])+abs(y[i+1]-y[i]);

        if(dt<distance){

            frag=false;

            break;

        }

        if((dt-distance)%2==0){

            frag=true;

            continue;

        }else{

            frag=false;

            break;

        }

    }

    

    if(frag==true){

        cout << "Yes" << endl;

    }else{

        cout << "No" << endl;

    }

    

    return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<string>

#include<map>

#include<vector>

#include<set>

#include<math.h>

using namespace std;



int main(){

    int N;

    cin >> N;

    vector<int> t(N+1, 0), x(N+1, 0), y(N+1, 0);

    for(int i=1; i<=N; i++){

        cin >> t.at(i) >> x.at(i) >> y.at(i);

    }

    

    int dt=0, distance=0;

    bool frag=true;

    

    for(int i=0; i<N; i++){

        dt=t.at(i+1)-t.at(i);

        distance=abs(x.at(i+1)-x.at(i))+abs(y.at(i+1)-y.at(i));

        if(dt<distance){

            frag=false;

            break;

        }

        if((dt-distance)%2==0){

            frag=true;

            continue;

        }else{

            frag=false;

            break;

        }

    }

    

    if(frag==true){

        cout << "Yes" << endl;

    }else{

        cout << "No" << endl;

    }

    

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <stdlib.h>



using namespace std;



int main(void)

{

  int N;

  int t[100001]={0};

  int x[100001]={0};

  int y[100001]={0};

  bool flag = false;

  

  cin >> N;

  for(int i = 1; i <= N; i++)

    cin >> t[i] >> x[i] >> y[i];



  for(int i = 1; i <= N; i++){

    int tt = t[i] - t[i - 1];

    int tx = abs(x[i] - x[i - 1]);

    int ty = abs(y[i] - y[i - 1]);

    int diff = tt-(tx+ty);

    

    if(diff < 0 || (abs(diff) % 2 == 1)){

      flag = true;

      break;

    }

  }



  cout << (flag ? "No" : "Yes") << endl;

    

  return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>



using namespace std;



int main()

{

  int N;

  cin >> N;

  

  vector<int> t(N+1), x(N+1), y(N+1);

  for (int i = 1; i <= N; i++) {

    cin >> t[i] >> x[i] >> y[i];

  }

  

  for (int i = 1; i <= N; i++) {

    int dist = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);

    if (t[i] - t[i-1] >= dist && (t[i] - t[i - 1])%2 == dist%2) {

    	;

    } else {

      cout << "No" << endl;

      return 0;

    }

  }

  cout << "Yes" << endl;

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<algorithm>

#include<cstring>

 

using namespace std;

typedef long long ll;

struct Info{int par, weight;};

const int MAX = 100005;

const int INF = (1<<28);



class UnionFind{

public:

  

  Info info[MAX];



  void init(int n){

    for(int i = 0; i < n; i++) info[i] = (Info){i,0};

  }

 

  Info find(int x){

    if(info[x].par == x) return info[x];

    

    Info tmp = find(info[x].par);

    info[x].weight += tmp.weight;

    info[x].par = tmp.par;

    return info[x];

  }



 

  

  void unite(int x, int y, int w){

    Info X = find(x);

    Info Y = find(y);

    //W[x]+w = W[y]

    

    info[Y.par].par = X.par;

    info[Y.par].weight += w+info[x].weight-info[y].weight;

  }

   

  bool same(int x, int y){

    return find(x).par == find(y).par;

  }



  int getValue(int x){return info[x].weight;}

};

 

int N,M;

bool used[MAX];

UnionFind uf;

 

void init(){

  memset(used,false,sizeof(used));

  uf.init(N+1);

}

 

 

void update(){

   

  int a,b,c;

  cin >> a >> b >> c;

  uf.unite(a,b,c);

}

 

void print(){

  int a,b;

  cin >> a >> b;

  if(uf.same(a,b)) cout << uf.getValue(b)-uf.getValue(a) << endl;

  else cout << "UNKNOWN" << endl;

}

 

int main(){

   

  while(cin >> N >> M && N+M){

    init();

    for(int i = 0; i < M; i++){

      char c;

      cin >> c;

      if(c == '!') update();

      else print();

    }

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cstdio>



using namespace std;

struct Info{int par, weight;};

const int MAX = 100005;



class UnionFind{

public:

  

  Info info[MAX];



  void init(int n){

    for(int i = 0; i < n; i++) info[i] = (Info){i,0};

  }

 

  Info find(int x){

    if(info[x].par == x) return info[x];

    

    Info tmp = find(info[x].par);

    info[x].weight += tmp.weight;

    info[x].par = tmp.par;

    return info[x];

  }



   void unite(int x, int y, int w){

    Info X = find(x);

    Info Y = find(y);

    //W[x]+w = W[y]

    

    info[Y.par].par = X.par;

    info[Y.par].weight += w+info[x].weight-info[y].weight;

  }

   

  bool same(int x, int y){

    return find(x).par == find(y).par;

  }



  int getValue(int x){return info[x].weight;}

};

 

int N,M;

UnionFind uf;

 

void update(){

  int a,b,c;

  scanf("%d %d %d\n",&a,&b,&c);

  uf.unite(a,b,c);

}

 

void print(){

  int a,b;

  scanf("%d %d\n",&a,&b);

  if(uf.same(a,b)) printf("%d\n",uf.getValue(b)-uf.getValue(a));

  else printf("UNKNOWN\n");

}

 

int main(){

   

 

  while(scanf("%d %d\n",&N,&M) && N+M){

    uf.init(N+1);

    for(int i = 0; i < M; i++){

      char c;

      scanf("%c",&c);

      if(c == '!') update();

      else print();

    }

  }

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn=100000;

int cnt=0;

int a[100010];

int prime[100010];

void init();

int main()

{

    ios::sync_with_stdio(false);

    int l,r;

    init();

    scanf("%d %d",&l,&r);

        int ans=0;

        for(int i=l;i<=r;i++)

        {

                int sum=0,n=i;

                for(int j=0;prime[j]*prime[j]<=n;j++)

                {

                    while(!(n%prime[j]))

                    {

                        n/=prime[j];

                        sum++;

                    }

                }

                if(n!=1)

                    sum++;

                if(!a[sum])

                    ans++;

        }

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

    return 0;

}

void init()

{

    a[1]=1;

    a[0]=1;



    for(ll i=2; i<=100000; i++)

    {

        if(!a[i])

        {

            prime[cnt++]=i;

            for(ll j=i*i; j<=100000; j+=i)

            {

                a[j]=1;

            }

        }

    }

}






// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstring>

#include<bitset>

#include<cstdio>

#define Re register

#define maxn 500005

std::bitset<maxn> f;

int p[maxn];

int l,r,ans;

int num[1000005],re[1000005];

int main()

{

	scanf("%d%d",&l,&r);

	f[0]=1;

	f[1]=1;

	for(Re int i=2;i<=35000;i++)

	{

		if(!f[i]) p[++p[0]]=i;

		for(Re int j=1;j<=p[0]&&p[j]*i<=35000;j++)

		{

			f[p[j]*i]=1;

			if(i%p[j]==0) break;

		}

	}

	for(Re int i=l;i<=r;i++) re[i-l]=i;

	for(Re int i=1;i<=p[0];i++)

	{

		for(Re int j=2;j*p[i]<=r;j++)

		if(p[i]*j>=l)

		{

			while(re[j*p[i]-l]!=1&&re[j*p[i]-l]%p[i]==0) re[j*p[i]-l]/=p[i],num[j*p[i]-l]++;

		}

	}

	for(Re int i=l;i<=r;i++)

	{

		if(re[i-l]!=1) num[i-l]++;

		if(!f[num[i-l]]) ans++;

	}

	std::cout<<ans;

	putchar(10);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=100005,maxm=400005;

int last[maxn],pre[maxm],other[maxm],t,cal[maxn],vis[maxn],q[maxn],head,tail;

int n,m,x,y;

void add(int x,int y)

{   

    ++t;

    pre[t]=last[x];

    last[x]=t;

    other[t]=y;

}

inline int read(void)

{

	int x=0,f=1;

     char ch=getchar();

     while(ch>'9'||ch<'0'){

       if(ch=='-') f=-1;

       ch=getchar(); }

     while(ch>='0'&&ch<='9'){

       x=x*10+ch-'0';

       ch=getchar();}

     return x*f;

}

int main()

{

	while(~scanf("%d%d",&n,&m))

	{

		ll I=0,P=0,Q=0;

		memset(last,0,sizeof(last));t=0;memset(vis,0,sizeof(vis));

		memset(pre,0,sizeof(pre));memset(other,0,sizeof(other));

		for(int i=1;i<=m;++i){

				x=read(),y=read();add(x,y);add(y,x);

		}

		for(int i=1;i<=n;++i)if(!vis[i])

		{

				head=tail=0;

				q[++tail]=i;

				cal[i]=0;

				vis[i]=1;

				bool flag=1;

				while(head<tail)

				{

    	              int u=q[++head];

    	              for(int j=last[u];j;j=pre[j])

					  {

    	                     int v=other[j];

    	                     if(!vis[v])

							 {

            	                q[++tail]=v;vis[v]=1;cal[v]=cal[u]+1;

           	              	 }

							 else

							 {

								 if((cal[v]-cal[u])%2==0)flag=0;

							 }

                       }

	            }

	  			if(head==1)

				{++I;continue;}

	  			if(flag)++Q;

	  			else ++P;

		}

		printf("%lld\n",2ll*I*n-I*I+P*P+2ll*P*Q+2ll*Q*Q);

    }

	return 0;

}

// Optimized solution to the same problem (faster):
#define _CRT_SECURE_NO_WARNINGS

#include <vector>

#include <iostream>

#include <string.h>

#include <set>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;



typedef double LD;

typedef long long LL;

typedef pair<int, int> PII;

#define MP make_pair

#define PB push_back

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)

#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)

#define REP(i, t) FOR(i,0,t)

#define ALL(a) a.begin(), a.end()

#define SZ(a) (int)((a).size())



const LL MOD = 1000000007;

const int INF = 1e9;

const LL LINF = 1LL * INF * INF;

const int MAXN = 100007;

const LD EPS = 1e-7;



vector <int> G[MAXN];

bool bip, used[MAXN];

int col[MAXN];



void dfs(int v)

{

	used[v] = true;

	REP(i, SZ(G[v]))

	{

		int to = G[v][i];

		if (!used[to])

		{

			col[to] = 3 - col[v];

			dfs(to);

		}

		if (col[to] != 3 - col[v])

			bip = false;

	}

}



int main()

{

	ios_base::sync_with_stdio(0);

	//freopen("In.txt", "r", stdin);

	int n, m;	

	cin >> n >> m;

	REP(i, m)

	{

		int u, v;

		cin >> u >> v;

		--u; --v;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	LL b = 0, c = 0, c1 = 0;

	REP(i, n)

	{

		if (SZ(G[i]) == 0)

		{

			++c1;

			continue;

		}

		if (!used[i])

		{

			bip = true;

			col[i] = 1;

			dfs(i);

			if (bip)

				++b;

			++c;

		}

	}

	cout << c * c + b * b + c1 * (2 * n - c1);

	//cout << endl; system("pause");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



const int N = 123456;



int n, m;

int color[N];

vector<int> g[N];



int main() {

  scanf("%d %d", &n, &m);

  for (int i = 0; i < m; i++) {

    int x, y;

    scanf("%d %d", &x, &y);

    x--; y--;

    g[x].push_back(y);

    g[y].push_back(x);

  }

  long long isolated = 0;

  long long bipart = 0;

  long long other = 0;

  fill_n(color, n, -1);

  for (int i = 0; i < n; i++) {

    if (color[i] != -1) {

      continue;

    }

    vector<int> que;

    que.push_back(i);

    color[i] = 0;

    bool bad = false;

    for (int i = 0; i < (int)que.size(); i++) {

      int v = que[i];

      for (int j = 0; j < (int)g[v].size(); j++) {

        int u = g[v][j];

        if (color[u] >= 0) {

          bad |= (color[v] == color[u]);

        } else {

          que.push_back(u);

          color[u] = 1 - color[v];

        }

      }

    }

    if ((int)que.size() == 1) {

      assert(!bad);

      isolated++;

    } else if (bad) {

      other++;

    } else {

      bipart++;

    }

  }

  long long ans = isolated * (2 * n - isolated) + 2 * bipart * bipart + 

    2 * bipart * other + other * other;

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

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



using ll = long long;



const int MAXN = 100010;

int N, M;

vector<int> adj[MAXN];

int col[MAXN];



int main() {

	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {

		int u, v; cin >> u >> v;

		adj[u].push_back(v);

		adj[v].push_back(u);

	}



	int nIsolated = 0;

	int nBipartite = 0;

	int nOther = 0;

	fill_n(col + 1, N, -1);

	for (int s = 1; s <= N; s++) {

		if (col[s] != -1) continue;

		vector<int> q = {s};

		col[s] = 0;

		bool isBip = true;

		for (size_t i = 0; i < q.size(); i++) {

			int cur = q[i];

			int colNxt = 1 - col[cur];

			for (size_t j = 0; j < adj[cur].size(); j++) {

				int nxt = adj[cur][j];

				if (col[nxt] == -1) {

					col[nxt] = colNxt;

					q.push_back(nxt);

				} else {

					isBip &= (col[nxt] == colNxt);

				}

			}

		}

		if (q.size() == 1) {

			nIsolated++;

		} else if (isBip) {

			nBipartite++;

		} else {

			nOther++;

		}

	}



	ll ans = 0;

	ans += ll(2) * nIsolated * N - ll(nIsolated) * nIsolated;

	ans += ll(2) * nBipartite * nBipartite;

	ans += ll(nOther) * nOther;

	ans += ll(2) * nOther * nBipartite;

	cout << ans << endl;



	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

typedef vector<int> VI;

typedef vector<VI> VVI;

typedef vector<ll> VL;

typedef vector<VL> VVL;

typedef pair<int, int> PII;



#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)

#define REP(i, n) FOR(i, 0, n)

#define ALL(x) x.begin(), x.end()

#define MOD 1000000007

#define INF (1LL<<25)     //33554432

#define PI 3.14159265359

#define EPS 1e-12

//#define int ll



VI g[100010];

int n, m, color[100010], d = 0;

bool e = true;



void dfs(int v, int c) {

  color[v] = c;

  d++;

  for(int i: g[v]) {

    if(color[i] == 0)

      dfs(i, -c);

    if(color[i] == c)

      e = false;

  }

}



signed main(void)

{

  cin >> n >> m;

  REP(i, m) {

    int u, v;

    cin >> u >> v;

    g[u-1].push_back(v-1);

    g[v-1].push_back(u-1);

  }



  ll a = 0, b = 0, c = 0;

  REP(i, n) {

    d = 0; e = true;

    if(color[i] == 0) {

      dfs(i, 1);

      if(d == 1) a++;

      else if(e) b++;

      else c++;

    }

  }

  //cout << a << " " << b << " " << c << endl;

  cout << 2*b*b + 2*b*c + c*c + a*a + 2*a*(n-a) << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)

#define REP(i, n) FOR(i, 0, n)

#define ALL(x) x.begin(), x.end()

template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }

template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }

struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;

#ifdef DEBUG_ 

#include "../program_contest_library/memo/dump.hpp"

#else

#define dump(...)

#endif

const ll INF = 1LL<<60;



int main(void) {

    ll n, m;

    cin >> n >> m;

    vector<vector<ll>> g(n);

    REP(i, m) {

        ll a, b;

        cin >> a >> b;

        a--, b--;

        g[a].push_back(b);

        g[b].push_back(a);

    }



    dump(g);



    bool flag;

    vector<ll> col(n, -1);

    function<void(ll,ll)> dfs = [&](ll v, ll c) {

        col[v] = c;

        for(auto to: g[v]) {

            if(col[to] == c) flag = false;

            if(col[to] == -1) dfs(to, 1-c);

        }

    };

    ll x = 0, y = 0, z = 0;

    REP(i, n) {

        if(g[i].size() == 0) z++;

        else if(col[i] == -1) {

            flag = true;

            dfs(i, 0);

            if(flag) x++;

            else y++;

        }

    }

    dump(x, y, z);

    cout << 2*x*x + 2*x*y + y*y + z*z + 2*z*(n-z) << endl;



    return 0;

}

// Fastest known solution for this problem: