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

#include<vector>

#include<set>

#include<queue>

using namespace std;



vector<int> v[100000], d(100000);

vector<bool> vis(100000, 0);



void dfs(int x, int dep){

    d[x] = dep;

    vis[x] = true;

    for(int y : v[x]){

        if(!vis[y]) dfs(y, dep+1);

    }

}



int main(){

    int n, a, b;

    cin >> n >> a >> b;

    a--, b--;

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

        int x, y;

        cin >> x >> y;

        x--, y--;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    dfs(a, 0);

    set<int> dist[n+5];

    for(int i = 0; i < n; i++)  if(i != b)  dist[d[i]].insert(i);

    int ans = 0;

    vector<bool> no(n, 0);

    queue<int> aoki;

    aoki.push(b);

    no[b] = true;

    set<int> even, odd;

    even.insert(a);

    while(true){

        // cout << ans << endl;

        // cout << "even ";

        // for(int x : even)   cout << x << " ";

        // cout << endl;

        // cout << "odd ";

        // for(int x : odd)   cout << x << " ";

        // cout << endl;



        for(int x : dist[ans+1]){

            if(no[x]) continue;

            if((ans+1)%2==0)    even.insert(x);

            else                odd.insert(x);

        }



        bool judge = false;

        if((ans+1)%2 == 0)  judge = even.empty();

        else                judge = odd.empty();

        if(judge){

            cout << ans << endl;

            return 0;

        }

        ans++;

        queue<int> naoki;

        while(!aoki.empty()){

            int x = aoki.front();   aoki.pop();

            for(int next : v[x]){

                if(no[next])  continue;

                no[next] = true;

                naoki.push(next);

                if(d[next]%2 == 0)   even.erase(next);

                else                 odd.erase(next);

            }

        }

        if(ans%2 == 1)      judge = odd.empty();

        else                judge = even.empty();

        if(judge){

            cout << ans << endl;

            return 0;

        }

        aoki = naoki;

    }

}

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

#include<vector>

#include<functional>

using namespace std;



int main(){

    int n, a, b;

    cin >> n >> a >> b;

    a--, b--;

    vector<int> v[n];

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

        int x, y;

        cin >> x >> y;

        x--, y--;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    function<void(vector<int>&,int,int,int)> f = [&](vector<int> &d, int x, int par, int dep){

        d[x] = dep;

        for(int y : v[x]){

            if(y != par)    f(d, y, x, dep+1);

        }

    };

    vector<int> tak(n), aoki(n);

    f(tak, a, -1, 0);

    f(aoki, b, -1, 0);

    int ret = 0;

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

        if(tak[i] < aoki[i])    ret = max(ret, aoki[i]-1);

    }

    cout << ret << endl;

    return 0;

}

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

using namespace std;



int a[100005],b[100005],c[100005];

vector<int>d[100006];

 

void dfs(int v,int s) {

	a[v]=a[s]+1;

	b[v]=1;

	c[v]=s;

	for(auto x:d[v]) {

		if(x==s) continue;

		dfs(x,v);

		b[v]=max(b[v],b[x]+1);

	}

	

}

int main(){

    int n,u,v;

    cin>>n>>u>>v;

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

		int x,y;

		cin>>x>>y;

		d[x].push_back(y);

		d[y].push_back(x);

	}

	dfs(v,0);

	int ans=-1;

	int dis=a[u]-a[v];

	

	dis=(dis-1)>>1;

//	cout<<dis<<endl;

	while(dis--){ 

	    u=c[u];

	}

	if(d[u].size()==1) 

	     ans=a[u]-2;

	else 

	    ans=b[u]+a[u]-3;

	    

	cout<<ans<<endl;

	



}


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

#include <cmath>

using namespace std;

const int N=1e5+5;

const int E=N<<1;

const int mod=1e9+7;

int n,u,v;

int a[N],b[N];

int d1[N],d2[N];

int h[N],nx[E],to[E];

int ec;

int ans;

void ae(int u,int v)

{

	ec++;

	nx[ec]=h[u];

	to[ec]=v;

	h[u]=ec;

}

void dfs(int u,int f,int d[])

{

	d[u]=d[f]+1;

	for (int i=h[u];i;i=nx[i])

		if (to[i]!=f)

			dfs(to[i],u,d);

}

int main()

{

	scanf("%d%d%d",&n,&u,&v);

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

	{

		scanf("%d%d",&a[i],&b[i]);

		ae(a[i],b[i]);

		ae(b[i],a[i]);

	}

	dfs(u,0,d1);

	dfs(v,0,d2);

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

		if (d1[i]<d2[i]&&d2[i]-2>ans)

			ans=d2[i]-2;

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

	return 0;

}

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

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



vector<int> G[200010];

int L[2][200010];





void dfs(int T, int V, int cost) {

    //cout << T << " " <<V << " " << cost << endl;

	L[T][V] = cost;

	for (auto to : G[V]){

		if (L[T][to] != INF) continue;

        if (T == 0)

		    dfs(T, to, cost + 1);

        else if (T == 1 && L[1][V] < L[0][V] && L[1][V] + 1 < L[0][to])

            dfs(T, to, cost + 1);

	}

}



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);



	int N, u, v;

	cin >> N >> u >> v;

    u--; v--;

	rep(i, N - 1) {

		int a, b;

		cin >> a >> b;

        a--; b--;

		G[a].push_back(b);

		G[b].push_back(a);

	}

	rep(i, 2) rep(j, 200010) L[i][j] = INF;

	dfs(0, v, 0);

	dfs(1, u, 0);

    int ans = 0;

    rep(i, N) {

        //cout << L[0][i] << " " << L[1][i] << endl;

        if (L[0][i] > L[1][i])

            ans = max(ans, L[0][i] - 1);

    }

    cout << ans << endl;



    return 0;

}


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

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000

vector<int> G[100010];

int d[2][100010];

void dfs(int x, int c, int p = -1, int depth = 0) {

    d[c][x] = depth;

    for(auto to: G[x]) {

        if(to == p) continue;

        if(c == 0)

            dfs(to, c, x, depth + 1);

        else if(d[0][x] >= depth + 1) {

            dfs(to, c, x, depth + 1);

        }

    }

}



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N, u, v;

    cin >> N >> u >> v;

    u--; v--;

    rep(i, N) d[1][i] = INF;

    rep(i, N - 1) {

        int a, b;

        cin >> a >> b;

        a--; b--;

        G[a].push_back(b);

        G[b].push_back(a);

    }

   dfs(v, 0); dfs(u, 1); 

    int ans = 0;

    rep(i, N) {

        //cout << "*" << d[0][i] << " " << d[1][i] << endl;

        if(d[1][i] != INF) ans = max(ans, d[0][i] - 1);

    }

    cout << ans << endl;





    return 0;

}


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

     

using namespace std;



map <int,double> dp[3000];



int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	int n;

	double t;

	vector <double> p;



	cin >> n;

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

	{

		cin >> t;

		p.push_back(t);

	}



	dp[0][0] = 1;

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

	{

		for(auto it : dp[i])

		{

			dp[i+1][it.first - 1] += it.second*(1 - p[i]);

			dp[i+1][it.first + 1] += it.second*(p[i]);

		}

	}



	double res = 0;



	for(auto it : dp[n])

	{

		if(it.first > 0)

		{

			res += it.second;

		}

	}



	cout << fixed;

	cout.precision(9);

	

	cout << res << '\n';



	return 0;

}


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

     

using namespace std;



double dp[3010][3010];



int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	int n;

	double t;

	vector <double> p;



	cin >> n;

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

	{

		cin >> t;

		p.push_back(t);

	}



	dp[0][0] = 1 - p[0];

	dp[0][1] = p[0];



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

	{

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

		{

			dp[i][j] += (dp[i-1][j])*(1 - p[i]);

			dp[i][j+1] += (dp[i-1][j])*(p[i]);

		}

	}



	double res = 0;



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

	{

		res += dp[n-1][i];

	}



	cout << fixed;

	cout.precision(9);



	cout << res << '\n';



	return 0;

}


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

#include<string.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

#include<iostream>

#include<iomanip>

#include<utility>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define fi first

#define sec second

#define pb push_back

#define mp make_pair

#define rep(a,b,c) for(int a=1;a<=b;a+=c)

#define repp(a,b,c,d) for(int a=b;a<=c;a+=d)



const double PI=acos(-1);

const double EPS=1e-12;

const int MOD=1e9+7;

const int INF=1<<30;





using namespace std;



double dat[3005][1505][2];

double p[3005];

int in;



double prob(int pos,int cnt,int phase){

	if(2*cnt>in)return dat[pos][cnt][phase]=0.0;

	if(pos==in)return dat[pos][cnt][phase]=1.0;

	if(dat[pos][cnt][phase]>-EPS)return dat[pos][cnt][phase];

	double temp=p[pos+1]*prob(pos+1,cnt,0)+(1.0-p[pos+1])*prob(pos+1,cnt+1,1);

	return dat[pos][cnt][phase]=temp;

}



int main(){

	//ios::sync_with_stdio(false);cin.tie(NULL);	cout.tie(NULL);

	cin>>in;

	double res;

	repp(j,0,1500,1){

		repp(k,0,1,1){

			dat[0][j][k]=-1e5;

		}

	}

	rep(i,in,1){

		cin>>p[i];

		repp(j,0,1500,1){

			repp(k,0,1,1){

				dat[i][j][k]=-1e5;

			}

		}

	}

	cout<<fixed<<setprecision(10)<<prob(0,0,0)<<endl;

	return 0;

}




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

#define INF 1073741824

#define ll long long

#define PI (2*acos(0.0))

#define p1(n) printf("showing %d\n",n)

#define p2(m,n) printf("showing %d %d\n",m,n)

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

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define pll pair<ll,ll>

#define x first

#define y second

#define on(val,pos) val|(1<<pos)

#define off(val,pos) val&(~(1<<pos))

#define check(val,pos) (val&(1<<pos))



//first four adjacent,second four corner

//int row[8]={0,-1,0,1,1,-1,-1,1};

//int col[8]={-1,0,1,0,-1,-1,1,1};

using namespace std;



int main(){

    ll i,j,k,n,m,t=0,cnt,test;

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

    cin>>n;

    double dp[n+5],head;

    memset(dp,0,sizeof dp);

    dp[0]=1;

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

        scanf("%lf",&head);

        for(int j=i+1;j>=0;j--){

            dp[j]=(j==0?0:dp[j-1]*head)+dp[j]*(1-head);

        }

    }

    double ans=0;

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

        ans+=dp[i];

    }

    printf("%.9lf",ans);

    //free();   //if pointer array

    return 0;

}


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

#include <sstream>

#include <vector>

#include <cmath>

#include <cstdio>

#include <queue>

#include <set>

#include <map>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#define maxn 100005

using namespace std;

typedef long long ff;

int fo[2*maxn+5];

long long kx[2*maxn+5],ty[2*maxn+5];



int fin(int x)

{

       if(fo[x]==x)

       return x;

       else

       return fo[x]=fin(fo[x]);



}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<2*maxn;i++)

    {fo[i]=i;

    ty[i]=0;

    kx[i]=0;

    }

    long long ans=0;

    int x,y;

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

    {

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

       fo[fin(x)]=fin(y+maxn);

     //  printf("%d\n",fo[fin(x)]);

      // fo[find(y+maxn)]=y;

    }

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

     kx[fin(i)]++;

     for(int i=maxn;i<maxn*2;i++)

     ty[fin(i)]++;



     for(int i=1;i<=2*maxn;i++)

     {

     ans+=kx[i]*ty[i];

    // if(kx[i]*ty[i]!=0)

     //printf("%d %d\n",i,kx[i]*ty[i]);

     }

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



}


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

#include <cctype>

#define int long long



const int MAXN = 100000;



int n, ans;

int f[200005], a1[200005], a2[200005];



int read() {

    int ret, f = 1;

    char ch;

    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);

    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');

    return ret * f;

}



void print(int x) {

    if(x < 0) putchar('-'), x = -x;

    if(x > 9) print(x / 10);

    putchar(x % 10 + '0');

}



void init(int x) {

    for(int i = 1; i <= x; ++i) f[i] = i;

}



int find(int x) {

    return f[x] == x ? x : f[x] = find(f[x]);

}



void merge(int x, int y) {

    f[find(x)] = find(y + MAXN);

}



signed main() {

    n = read();

    init(MAXN << 1);

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

        merge(read(), read());

    for(int i = 1; i <= MAXN; ++i) ++a1[find(i)];

    for(int i = MAXN + 1; i <= MAXN << 1; ++i) ++a2[find(i)];

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

        ans += a1[i] * a2[i];

    return print(ans - n), 0;

}

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

using namespace std;

 

int main(){

  int l, r, t = 0;

  scanf("%d", &l);

  for(r = 0; (1<<r) <= l; r++); r--;

  for(int i = l; i; i -= i&-i, t++); t--;

  printf("%d %d\n", r+1, 2*r+t);

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

    printf("%d %d %d\n", i+1, i+2, 1<<i);

    printf("%d %d %d\n", i+1, i+2, 0);

    if(l&(1<<i)) printf("%d %d %d\n", i+1, r+1, l-=l&-l);

  }

}

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



int main(){

  int l, r = 0, t = 0;

  scanf("%d", &l);

  for(; (1<<r) <= l; r++) if(l&(1<<r)) t++;

  printf("%d %d\n", r, 2*r+t-3);

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

    printf("%d %d %d\n%d %d %d\n", i, i+1, 1<<(i-1), i, i+1, 0);

    if(l&(1<<(i-1))) printf("%d %d %d\n", i, r, l-=l&-l);

  }

}

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

#include <tuple>

#include <queue>



int main(void){

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

    int n = 0; while((1 << (n+1)) <= L) n++;

    std::queue<std::tuple<int, int, int>> Q;

    for(int x = 0; x + 1 <= n; ++x) Q.emplace(x, x+1, 0), Q.emplace(x, x+1, 1 << x);

    int N = (1 << n) - 1; int U = L - N - 1;

    int l = L;

    for(int d = n; d >= 0; --d) if((U >> d) & 1){ // 101

        Q.emplace(d, n, l - (1 << d) ); l -= (1 << d);

    }



    printf("%d %lu\n", n+1, Q.size());

    while(not Q.empty()){

        int x, y, c; std::tie(x, y, c) = Q.front(); Q.pop();

        printf("%d %d %d\n", x + 1, y + 1, c);

    }

    return 0;

}

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

int main(void){

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

    int n = 0; while((1 << (n+1)) <= L) n++;

    int N = (1 << n) - 1; int U = L - N - 1;

    int l = L;

    int m = 2 * n + __builtin_popcount(U);

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

    for(int x = 0; x + 1 <= n; ++x) printf("%d %d 0\n%d %d %d\n", x+1, x+2, x+1, x+2, (1 << x));

    for(int d = n; d >= 0; --d) if((U >> d) & 1){

        l -= (1 << d);

        printf("%d %d %d\n", d+1, n+1, l);

    }

    return 0;

}

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

struct edge{

	int x,y,co;

}e[125];

int n,l,m,cnt;

void ins(int a,int b,int c)

{

	e[++cnt].x=a;e[cnt].y=b;e[cnt].co=c;

}

int main()

{

	scanf("%d",&l);

	n=floor(log2(l))+1;

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

	{

		ins(i,i+1,1<<(i-1));

		ins(i,i+1,0);

	}

	int now=0;int fu=1<<(n-1);

	while(l>1)

	{

		if(l&1)

		{

			ins(now+1,n,fu);

			fu|=1<<now;

		}

		l>>=1;

		now++;

	}

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

	for(int i=1;i<=cnt;i++) printf("%d %d %d\n",e[i].x,e[i].y,e[i].co);

}

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



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

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

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

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

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

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

using namespace std;

struct E{int u,v,c;};

int l,p=1,mx,n,s1;

vector<E> ans;

int main(){

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

	int i;

	for(i=1;mx+p<=l;++i){

		ans.push_back({i,i+1,p});

		ans.push_back({i,i+1,0});

		mx+=p,p*=2;

	}

	n=i--,p/=2,s1=mx-p;

	while(mx<l){

		if(mx+s1+1<=l)ans.push_back({i,n,mx+1}),mx+=s1+1;

		p/=2,s1-=p,i--;

	}

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

	for(int i=0;i<ans.size();++i)printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].c);

} 

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



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

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

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

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

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

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



#define maxn 100005



using namespace std;

typedef long long ll;



int main(){



  ios_base::sync_with_stdio(0);



  int L;

  cin >> L;

  L--;



  cout << 20 << ' ';



  vector < int > u, v, c;

  #define add(x, y, z) {u.push_back(x); v.push_back(y); c.push_back(z);}



  int i;



  for (i = 19; i > 0 && L > (1 << (19 - i)); --i){

    add(i, i + 1, 0);

    add(i, i + 1, (1 << (19 - i)));

    L -= (1 << (19 - i));

  }



  if (i) add(i, i + 1, 0);



  int val = (1 << (19 - i));



  for (int is = 0; is <= 20; ++is) {

    if ((L >> is)&1) {

      add(max(i, 1), 20 - is, val);

      val += (1 << is);

    }

  }



  while ((--i) > 0)

    add(i, i + 1, 0);



  cout << u.size() << '\n';



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

    cout << u[i] << ' ' << v[i] << ' ' << c[i] << '\n';

  return 0;



}


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



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

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

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

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

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

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

using namespace std;



int n, m, L;

vector<pair<int, int>> adj[25];



void addEdge(int u, int v, int w) {

  ++m;

  adj[u].emplace_back(v, w);

}



int main() {

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

  cin >> L;

  int r = 0;

  while (1 << (r + 1) <= L) ++r;

  n = r + 1;

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

    addEdge(i, i + 1, 0);

    addEdge(i, i + 1, 1 << (i - 1));

  }

  int done = (1 << r) - 1;

  while (done < L - 1) {

    int t = 1;

    while (done + (1 << t) < L) ++t;

    addEdge(t, n, done + 1);

    done += 1 << (t - 1);

  }

  cout << n << " " << m << "\n";

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

    for (auto &p: adj[i])

      cout << i << " " << p.first << " " << p.second << "\n";

  return 0;

}

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



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

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

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

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

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

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

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

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

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

#define pb          push_back

#define inf         2e9+5

#define mp          make_pair

#define ll          long long

#define pii         pair<int,int >

#define fileout     freopen("output.txt","w",stdout)

#define filein      freopen("input.txt","r",stdin)

#define mem(x,i)    memset(x,i,sizeof x)

#define PI          acos(-1.0)

#define ff          first

#define ss          second

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

#define Case(t)     for(int ks=1;ks<=t;ks++)

#define sf          scanf

#define pf          printf

/*------------------------------Graph Moves----------------------------*/

const int fx[]= {+1,-1,+0,+0};

const int fy[]= {+0,+0,+1,-1};

//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move

//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move

//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

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

using namespace std;

//using namespace __gnu_pbds;

//

//template <typename T>  using orderedSet =

//    tree<T, null_type, less<T>,

//    rb_tree_tag, tree_order_statistics_node_update>;//find_by_order,order_of_key

//



ll dp[2020][2020];

const int mod=1000000007;

void nCr()

{

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

    {

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

        {

            if(j==0 || j==i) dp[i][j]=1;

            else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;

        }

    }

}



bool vis[1000006];

int main()

{

    int n,n2;

    cin>>n;n2=n;

    vector<pii>adj[30];

    int lg=log2(n);

    int edge=0;

    for(int i=2;i<=lg+1;i++)

    {

        adj[i-1].pb({i,0});

        adj[i-1].pb({i,(1<<(i-2))});

        edge+=2;

    }



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

    {

        if(n &(1<<i))

        {

            adj[i+1].pb({lg+1,n2-(1<<i)});

            n2-=(1<<i);

            edge++;

        }

    }

    cout<<lg+1<<' '<<edge<<endl;

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

    {

        for(pii p:adj[i])

        {

            cout<<i<<' '<<p.ff<<' '<<p.ss<<endl;

        }

    }

}


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



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

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

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

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

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

// Fastest known solution for this problem: