stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e3+5;

vector<pair<ll,ll> >v(N);//vector对pair排序时按'键'排序 即第一元素first 

ll dp[N][N];

int n;

ll fun(int l,int r){

	if(l>r) return 0;

	if(dp[l][r]) return dp[l][r];

	int i=n-(r-l+1);//当前要放入的数的下标 

	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));//放两端取最大 

}

int main(){

	scanf("%d",&n);

	for(int i=0,x;i<n;i++)

		scanf("%d",&x),v.push_back({x,i});

	sort(v.rbegin(),v.rend());//贪心从大到小排 

	fun(0,n-1);

	printf("%lld\n",dp[0][n-1]);

	return 0;

}

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

#include <algorithm>

#include <vector>

#include <utility>

using namespace std;



typedef long long LL;

typedef pair <LL, LL> PII;



vector<PII> a;

LL dp[2005][2005];

int n;



LL solve(int l, int r){

	if (l > r) return 0;

	if (dp[l][r]) return dp[l][r];

	int i = n - (r - l + 1);

	return dp[l][r] = max(solve(l, r - 1) + a[i].first * (r - a[i].second), solve(l + 1, r) + a[i].first * (a[i].second - l));

}



int main(){

	scanf("%d", &n);

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

		int x;

		scanf("%d", &x);

		a.push_back({x, i});

	}

	sort(a.rbegin(), a.rend());

	solve(0, n - 1);

	printf("%lld\n", dp[0][n - 1]);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e3+5;

vector<pair<ll,ll> >v(N);

ll dp[N][N];

int n;

ll fun(int l,int r){

	if(l>r) return 0;

	if(dp[l][r]) return dp[l][r];

	int i=n-(r-l+1);

	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));

}

int main(){

	scanf("%d",&n);

	for(int i=0,x;i<n;i++)

		scanf("%d",&x),v.push_back({x,i});

	sort(v.rbegin(),v.rend());

	fun(0,n-1);

	printf("%lld\n",dp[0][n-1]);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=2e3+5;

ll dp[N][N];

struct p{

	int x,id;

	bool operator<(const p&a)const{

		return x>a.x; 

	}

}a[N];

int main(){

	int n;

	scanf("%d",&n);

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

		scanf("%d",&a[i].x),a[i].id=i;

	sort(a+1,a+n+1);//从大到小排序 

	for(int k=1;k<=n;k++)//对第k个元素进行放置(前k-1个元素所有情况都已知) 

		for(int i=0;i<k;i++)//遍历前k-1元素的所有情况. i为往左放置的个数. 

		{

			int j=k-1-i;//前k-1元素往右放置的个数. 

			dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(ll)a[k].x*(a[k].id-(i+1)));//往左放 

			dp[i][j+1]=max(dp[i][j+1],dp[i][j]+(ll)a[k].x*(n-j-a[k].id));//往右放 

		}

	ll ans=0;

	for(int i=0;i<=n;i++) ans=max(ans,dp[i][n-i]);//取最大值. 

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

	return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <cstdio>

#include <iostream>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <bitset>

#include <cstring>

#include <deque>

using namespace std;

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define CLR(mat) memset(mat, 0, sizeof(mat))

typedef long long ll;

ll n, m, k;

map<ll, ll> MAP;

ll num;

void dfs(int cnt) {

  if(cnt == n) {

    MAP[max(1LL, num-k)]++;

  } else {

    FOR(i,1,m+1) {

      num += i;

      dfs(cnt+1);

      num -= i;

    }

  }

}

int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  while(cin>>n>>m>>k,n||m||k) {

    num = 0;

    MAP.clear();

    ll waru = pow(m, n);

    dfs(0);

    double ans = 0;

    for(auto M : MAP) {

      ans += (double)M.first * M.second / waru;

    }

    printf("%.10lf\n", ans);

  }

  return 0;

}

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

#include <cstdio>

#include <iostream>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <bitset>

#include <cstring>

#include <deque>

using namespace std;

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define CLR(mat) memset(mat, 0, sizeof(mat))

typedef long long ll;

int main()

{

  ll n,m,k;

  while(cin>>n>>m>>k,n||m||k) {

    ll dp[n+1][n*m+1]; CLR(dp);

    dp[0][0] = 1;

    FOR(i,0,n) {

      FOR(j,0,m*i+1) {

        FOR(t,1,m+1) {

          dp[i+1][j+t] += dp[i][j];

        }

      }

    }

    double ans = 0;

    ll waru = pow(m, n);

    FOR(i,0,n*m+1) {

      ans += (double)dp[n][i] * max(1LL, i-k) / waru;

    }

    printf("%.10lf\n", ans);

  }

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cmath>



using namespace std;



int n, m, k, x;

double ans;



void dfs(int node, int sum) {

    if (node == n) {

        if (sum-k < 1) sum = 1;

        else sum -= k;

        ans += (double)sum / x;

        return;

    }

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

        dfs(node+1, sum+i);

    }

    return;

}



int main(void){

    while (cin>>n>>m>>k && n) {

        ans = 0;

        x = pow(m,n);

        dfs(0, 0);

        printf("%.12lf\n",ans);

    }

}

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

#include <cstdio>

#include <vector>

#include <cmath>



using namespace std;



int main(void){

    int n, m, k;

    while (cin>>n>>m>>k && n) {

        vector<vector<int> > dp(n+1, vector<int>(n*m+1, 0));

        dp[0][0] = 1;

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

            for (int j = 0; j < n*m+1; j++) {

                if (dp[i][j] == 0) continue;

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

                    dp[i+1][j+dice] += dp[i][j];

                }

            }

        }

        

        double ans = 0;

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

            if (dp[n][i] == 0) continue;

            if (i-k < 1) ans += 1 * dp[n][i];

            else ans += (i-k) * dp[n][i];

        }

        printf("%.12lf\n", ans / pow(m,n));

    }

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cmath>



using namespace std;



int n, m, k;

double ans;



void dfs(int node, int sum) {

    if (node == n) {

        if (sum-k < 1) sum = 1;

        else sum -= k;

        ans += sum;

        return;

    }

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

        dfs(node+1, sum+i);

    }

    return;

}



int main(void){

    while (cin>>n>>m>>k && n) {

        ans = 0;

        dfs(0, 0);

        printf("%.12lf\n", ans / pow(m,n));

    }

}

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

#include <cstdio>

#include <vector>

#include <cmath>



using namespace std;



int main(void){

    int n, m, k;

    while (cin>>n>>m>>k && n) {

        vector<vector<int> > dp(n+1, vector<int>(n*m+1, 0));

        dp[0][0] = 1;

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

            for (int j = 0; j < n*m+1; j++) {

                if (dp[i][j] == 0) continue;

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

                    dp[i+1][j+dice] += dp[i][j];

                }

            }

        }

        

        double ans = 0;

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

            if (dp[n][i] == 0) continue;

            if (i-k < 1) ans += 1 * dp[n][i];

            else ans += (i-k) * dp[n][i];

        }

        printf("%.12lf\n", ans / pow(m,n));

    }

}
// Slower C++ solution:
#include <iostream>

#include <iomanip>

#include <vector>

#include <algorithm>



using namespace std;



vector<int> buffer;



int dfs(int m, int sum, int rem){

        if(rem == 0){

                ++(buffer[sum]);

                return 1;

        }

        int retval = 0;

        for(int i = 1; i <= m; ++i){ retval += dfs(m, sum + i, rem - 1); }

        return retval;

}



int main(){

        cout << setprecision(10);

        while(true){

                int n, m, k;

                cin >> n >> m >> k;

                if(n == 0 && m == 0 && k == 0){ break; }

                buffer.resize(n * m + 1);

                fill(buffer.begin(), buffer.end(), 0);

                int num = dfs(m, 0, n);

                double answer = 0.0;

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

                        if(i <= k){

                                answer += 1.0 * buffer[i] / num;

                        }else{

                                answer += (double)(i - k) * buffer[i] / num;

                        }

                }

                cout << answer << endl;

        }

        return 0;

}

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

#include <iomanip>

#include <string>

#include <vector>

#include <algorithm>



using namespace std;



int main(){

	ios_base::sync_with_stdio(false);

	cout << setiosflags(ios::fixed) << setprecision(10);

	while(true){

		int n, m, k;

		cin >> n >> m >> k;

		if(n == 0 && m == 0 && k == 0){ break; }

		double answer = 0;

		if(n == 1){

			const double r = 1.0 / m;

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

				answer += max(1, i - k) * r;

			}

		}else{

			const double r = 1.0 / m;

			const int len = n * m + 1;

			vector<double> dp(len);

			dp[0] = 1.0;

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

				vector<double> next(len);

				for(int j = 0; j + m < len; ++j){

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

						next[j + k] += r * dp[j];

					}

				}

				dp.swap(next);

			}

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

				answer += dp[i] * max(1, i - k); 

			}

		}

		cout << answer << endl;

	}

	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int r;

    cin>>r;

    if(r>0&&r<101)

    {

        r=r*r;

        cout<<r<<endl;

    }

    return 0;

}


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

int main()

{

    int i;

    scanf("%d",&i);

    printf("%d",i*i);

    return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int r;

    cin>>r;

    if(r>0&&r<101)

    {

        r=r*r;

        cout<<r<<endl;

    }

    return 0;

}


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

#include<math.h>



int main()

{

   int a,m;



   scanf("%d",&a);



   m = pow(a,2);



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



   return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int r;

    cin>> r;

    cout<<r*r<<endl;



    return 0;

}

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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	int k;

	cin>>k;

	cout<<k*k<<endl;

	

	

}

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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int R,a;

    cin>>R;

    a=R*R;

    cout<<a;

}






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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

int r;

cin>>r;

cout<<r*r<<endl;



return 0;







}




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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int r;

    cin>> r;

    cout<<r*r<<endl;



    return 0;

}

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

int main(){

	int r; 

	scanf("%d", &r);

	printf("%d\n", r*r);



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	int k;

	cin>>k;

	cout<<k*k<<endl;

	

	

}

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

int main(){

	int r; 

	scanf("%d", &r);

	printf("%d\n", r*r);



	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int R,a;

    cin>>R;

    a=R*R;

    cout<<a;

}






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

int main(){

	int r; 

	scanf("%d", &r);

	printf("%d\n", r*r);



	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

int r;

cin>>r;

cout<<r*r<<endl;



return 0;







}




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

int main(){

	int r; 

	scanf("%d", &r);

	printf("%d\n", r*r);



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long 

#define mod 1000000007

#define first f

#define second s

#define N 1000000

vector<ll>v(N);

ll l,m,n,sum,ans,maximum,minimum,mahakal,a,b,c,t,i,j,k;

ll cnt,cnt1,cnt2,cnt3;

string str,str1;

ll arr[N];

int main(){

    cin>>n;

  cout<<n*n<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 9.465580552719496x):
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂

                   

                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            

 

 */ 

#include<bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long 

#define mod 1000000007

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define _it iterator

#define all(_x) _x.begin(),_x.end()

#define f first

#define s second

#define pb push_back

void mahakal(){

	#ifndef ONLINE_JUDGE

	freopen("input.txt","r",stdin);

	freopen("output.txt","w",stdout);

	freopen("error.txt","w",stderr);

	#endif

}

int main(){

	//mahakal(),fast;

	

	ll r ;

	cin>> r ;

	ll ans = r*r ;

	cout<<ans<<endl;



	return 0;

}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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



int main()

{

    int in ;

    long long int value;

    scanf("%d",&in);

    value =(long long)in * in ;

    printf("%lld",value);

    return 0;



}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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



int main()



{



int a,d;



double b=3.1415926535,c;



scanf("%d",&a);



c=(double)(b*a*a);



d=(int)(c/b);



printf("%d",d);



return 0;



}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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

int main()

{

    int r,rad;

    scanf("%d", &r);

    rad = (r*r);

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

}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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

int main()

{

   int r,result;

   scanf("%d",&r);

   result=r*r;

   printf("%d",result);

   return 0;

}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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



int main()

{

	long long int num, save;

	scanf("%lld", &num);



	printf("%lld\n", num*num);

}
// Slower C++ solution:
#include<iostream>



using namespace std ;



int main()



{

    int r ;



    cin>>r ;



    cout<<r*r<<endl ;



    return 0;

}

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



int main() {

	int a;

	

	scanf("%d", &a);

	

	printf("%d\n", a*a);



	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int r;

    cin>>r;

    cout<<r*r<<endl;

    return 0;

}


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

int main()

{

    int r;

    scanf("%d", &r);

    r=r*r;

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int r;

    cin>>r;

    cout<<r*r<<endl;

    return 0;

}


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

int main() {

	int r;

	scanf("%d",&r);

	printf("%d\n",r*r);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int a[100001];

int N, i, cnt;

main(){

    cin >> N;

    for(; i<N; i++) cin >> a[i];

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

        if(a[a[i] - 1] - 1 == i){

            cnt++;

        }

    }

    cout << cnt / 2 << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.230281099691152x):
#import<stdio.h>

int a[100010],b,i,s;main(){scanf("%d",&b);for(;i-b;++i)scanf("%d",a+i+1);for(i=1;i<=b;++i){i==a[a[i]]?++s:0;}printf("%d\n",s/2);}
// Slower C++ solution:
#include<iostream>

#include<string.h>

#include<cstdio>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<cmath>

#include<utility>

#define ll long long int

#define ld long double

#define INF 1000000000

#define EPS 0.0000000001

#define rep(i,n) for(i=0;i<n;i++)

using namespace std;

typedef pair<int, int> P;



string str;



int main()

{

  int n,i;

  int a[1000000];

  bool p[1000000];





  cin>>n;

  p[0]=false;



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

    cin>>a[i];

    p[i]=false;

  }



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

    if(a[a[i]]==i){

      p[i]=true;

      p[a[i]]=true;

    }

  }

  int ans=0;

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

    if(p[i])

      ans++;

  cout<<ans/2<<endl;

}


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

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<math.h>

#include<string>

#include<string.h>

#include<stack>

#include<queue>

#include<vector>

#include<utility>

#include<set>

#include<map>

#include<stdlib.h>

#include<iomanip>



using namespace std;



#define ll long long

#define ld long double

#define EPS 0.0000000001

#define INF 1e9

#define MOD 1000000007

#define rep(i,n) for(i=0;i<n;i++)

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

#define all(in) in.begin(),in.end()

#define shosu(x) fixed<<setprecision(x)



typedef vector<int> vi;

typedef pair<int,int> pii;



int main(void) {

  int i,j;

  int n;

  cin>>n;

  vi a(n);

  rep(i,n)cin>>a[i],a[i]--;

  int ans=0;

  rep(i,n)if(a[a[i]]==i)ans++;

  cout<<ans/2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define rep(i,n)for(int i=0;i<n;i++)

#define EPS (1e-10)

#define MOD 1000000007

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef pair<int, int>P;



int s[100000];

int main() {

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

	int cnt = 0;

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

		int a; scanf("%d", &a);

		if (s[a] == i)cnt++;

		s[i] = a;

	}

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

}

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



int s[100001];

int main() {

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

	int cnt = 0;

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

		int a; scanf("%d", &a);

		if (s[a] == i)cnt++;

		s[i] = a;

	}

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

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define rep(i,n)for(int i=0;i<n;i++)



int s[100001];

int main() {

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

	int cnt = 0;

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

		int a; scanf("%d", &a);

		if (s[a] == i)cnt++;

		s[i] = a;

	}

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

}

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



int s[100001];

int main() {

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

	int cnt = 0;

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

		int a; scanf("%d", &a);

		if (s[a] == i)cnt++;

		s[i] = a;

	}

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

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#define maxn 10000

using namespace std;



int bcj[maxn + 100], n, m;



int Find(int x){

	if(bcj[x] < 0)

		return x;

	return bcj[x] = Find(bcj[x]);

}



void Union(int x, int y){

	x = Find(x);

	y = Find(y);

	if(x == y)

		return;

	bcj[x] += bcj[y];

	bcj[y] = x;

}



int main(){

	cin >> n >> m;

	int choice, x, y;

	memset(bcj, -1, sizeof(bcj));

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

		cin >> choice >> x >> y;

		if(choice == 0){

			Union(x, y);

		}

		else{	

			cout << (Find(x) == Find(y)) << endl;

		}

	}

	return 0;

}


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

#include <vector>



class DisjointSet

{

public:

	DisjointSet(int n)

	{

		p.resize(n, 0);

		rank.resize(n, 0);

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

			MakeSet(i);

	}



	void MakeSet(int x)

	{

		p[x] = x;

		rank[x] = 0;

	}



	bool Same(int x, int y)

	{

		return FindSet(x) == FindSet(y);

	}



	int FindSet(int x)

	{

		if (p[x] != x)

			p[x] = FindSet(p[x]);

		return p[x];

	}



	void Unit(int x, int y)

	{

		Link(FindSet(x), FindSet(y));

	}



	void Link(int x, int y)

	{

		if (rank[x] > rank[y])

			p[y] = x;

		else

		{

			p[x] = y;

			if (rank[x] == rank[y])

				rank[y]++;

		}

	}



private:

	std::vector<int> p, rank;

};



int main()

{

	int n, q, c, x, y;

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

	DisjointSet ds(n);



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

	{

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

		//printf("T %d %d %d\n", c, x, y);

		if (c == 0)

			ds.Unit(x, y);

		else

			printf("%d\n", ds.Same(x, y) ? 1 : 0);

	}



	return 0;

}