stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.410129807946543x):
#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<string.h>

using namespace std;

int N;

int pret,prex,prey,t,x,y;

int ans=1;

int main(){

    scanf("%d",&N);

    pret=0;prex=prey=0;

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

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

        //cout<<t<<" "<<x<<" "<<y<<endl;

        int time = t - pret;

        int needtime = abs(prex-x) + abs(prey-y);

       // cout<<"time："<<time<<endl<<"needtime:"<<needtime<<endl;

        if(ans&&time>=needtime&&((time-needtime)%2==0))ans=1;

        else {ans=0;}

       // cout<<"ans:"<<ans<<endl;

        pret=t;prex=x;prey=y;

}

    if(ans)printf("Yes");

    else printf("No");

    return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3950366463339332x):
#include <bits/stdc++.h>

using namespace std;



#define      ll     long long int



const int N = 100005;



int main()

{

    int n, i, j, k, x, d, t, lt = 0, y, x0, y0, fl = 1;

    cin >> n;

    x0 = 0;

    y0 = 0;

    lt = 0;

    while (n--) {

        cin >> t >> x >> y;

        d = abs(x - x0) + abs(y - y0);

        if ( !(d <= (t - lt) && d % 2 == (t - lt) % 2) ) {

            fl = 0;

        }

        lt = t;

        x0 = x;

        y0 = y;

    }

    if (fl) {

        cout << "Yes\n";

    }

    else {

        cout << "No\n";

    }

    return 0;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.5515041459509225x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 3.4027186829871647x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.193174083271061x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.1983259197870106x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.1983128457822967x):
#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]);

	int diff = (t[i] - t[i - 1]) - dist;

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

   		cout << "No" << endl;

      	return 0;

    }

  }

  cout << "Yes" << endl;

  

  return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1304086607801667x):
#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;

}
// Slower C++ solution:
#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;

            }

        }

    }

}






// Faster C++ solution for the same problem (measured speedup: 1.6664366983354266x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1904367017118327x):
#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;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



#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 ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



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

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 100000 + 47;

const int MOD = 1000 * 1000 * 1000 + 7;



vector<int> g[MAX];

int C[MAX];

int numb;

bool is;

LL o, e, iz;



void dfs(int v, int c)

{

	if (C[v] != -1)

	{

		if (C[v] != c) is = false;

		return;

	}



	numb++;

	C[v] = c;

	FOR(i, 0, SZ(g[v]))

	{

		int to = g[v][i];

		dfs(to, c ^ 1);

	}

}



int main()

{

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

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	int n, m;

	cin >> n >> m;

	FOR(i, 0, m)

	{

		int a, b;

		cin >> a >> b;

		a--;

		b--;

		g[a].push_back(b);

		g[b].push_back(a);

	}

	

	FILL(C, -1);

	FOR(i, 0, n)

	{

		if (C[i] == -1)

		{

			numb = 0;

			is = true;

			dfs(i, 0);



			if (numb == 1)

			{

				iz++;

				continue;

			}



			if (is) e++; else o++;

		}

	}



	//cout << res << endl;

	LL res = 2 * e * e + o * o + 2 * o * e + n * iz + iz * (n - iz);

	cout << res << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1481453995094533x):
#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const long long MAXN=100005;

long long n,m;

vector<int>w[MAXN];

bool vis[MAXN];

long long cl[MAXN];

bool dfs(long long u)

{

	vis[u]=1;

	long long re=1;

	for(long long i=0;i<int(w[u].size());i++)

	{

		long long v=w[u][i];

		if(vis[v])

			re&=(cl[u]!=cl[v]);

		else

		{

			cl[v]=cl[u]^1;

			re&=dfs(v);

		}

	}

	return re;

}

int main()

{

	//freopen("squared.in","r",stdin);

	//freopen("squared.out","w",stdout);

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

	for(long long i=1;i<=m;i++)

	{

		long long u,v;

		scanf("%lld %lld",&u,&v);

		w[u].push_back(v);

		w[v].push_back(u);

	}

	long long I=0,O=0,J=0;

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

	{

		if(!vis[i])

		{

			if(int(w[i].size())==0)

				I++;

			else if(dfs(i))

				O++;

			else

				J++;

		}

	}

	printf("%lld\n",I*I+I*(n-I)*2+O*O*2+J*J+O*J*2);

	fclose(stdin);

	fclose(stdout);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.1542782396311937x):
#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;

}