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

using namespace std;

typedef long long lint;

typedef long double llf;

typedef pair<lint, lint> pi;

const int MAXN = 2005, N = MAXN;

const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;

int dp[MAXN][3][MAXN], odp[3][MAXN], sz[MAXN];

vector<int> adj[N];

void sadd(int &x, int y) {

	x += y;

	while (x >= mod) x -= mod;

}

void dfs(int v, int p = -1) {

	dp[v][0][1] = 1;

	sz[v] = 1;

	for (int u : adj[v]) {

		if (u != p) {

			dfs(u, v);

			memcpy(odp, dp[v], sizeof dp[v]);

			memset(dp[v], 0, sizeof dp[v]);

			for (int dv = 0; dv <= 2; ++dv) {

				for (int du = 0; du <= 2; ++du) {

					for (int use = 0; use <= 1; ++use) {

						if (use == 1 && (du > 1 || dv > 1)) continue;

						for (int cv = 1; cv <= sz[v]; ++cv)

							for (int cu = 1; cu <= sz[u]; ++cu) {

								int ways = (use == 1 ? mod - 1 : 1);

								if (use) {

									if (du == 0 && dv == 0) 

										ways = (long long) ways * 2 % mod;

									if (du == 1 && dv == 1)

										ways = (long long) ways * inv2 % mod;

								}

								sadd(dp[v][dv + use][cv + cu - use], 

										odp[dv][cv] * (long long) dp[u][du][cu] % mod * ways % mod);

							}



					}

				}

			}

			sz[v] += sz[u];

		}

	}

	

}

int f[N];

int main(){

	f[0] =1 ;

	for (int j = 1; j < N; ++j) f[j] = (long long) f[j - 1] * j % mod;

	int n;

	cin >> n;

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

		int p;

		cin >> p;

		adj[--p].push_back(j);

	}

	dfs(0);

	int res = 0;

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



		for (int d = 0; d <= 2; ++d) if (dp[0][d][j]) {

			sadd(res, dp[0][d][j] * (long long) f[j] % mod);

		//	cout << " hi " << d << ' ' << j << ' ' << dp[0][d][j] << endl;

		}

	cout << res << endl;

	

}




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

using namespace std;

typedef long long lint;

typedef pair<int, int> pi;

const int MAXN = 2005;

const int mod = 1e9 + 7;



int n, sz[MAXN], p[MAXN];

vector<int> gph[MAXN];



lint dp[MAXN][MAXN][2];

lint fact[MAXN];

lint aux[MAXN][3], nxt[MAXN][3];



int main(){

	fact[0] = 1;

	for(int i=1; i<MAXN; i++) fact[i] = fact[i-1] * i % mod;

	cin >> n;

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

		cin >> p[i];

		gph[p[i]].push_back(i);

	}

	for(int i=n; i; i--){

		memset(aux, 0, sizeof(aux));

		aux[0][0] = 1;

		for(auto &j : gph[i]){

			memset(nxt, 0, sizeof(nxt));

			for(int k=0; k<=sz[j]; k++){

				for(int l=0; l<=sz[i]; l++){

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

						nxt[k + l][m] += dp[j][k][0] * aux[l][m] % mod;

						if(m < 2) nxt[k + l + 1][m+1] += dp[j][k][1] * aux[l][m] % mod;

					}

				}

			}

			sz[i] += sz[j];

			for(int j=0; j<=sz[i]; j++){

				for(int k=0; k<3; k++) aux[j][k] = nxt[j][k] % mod;

			}

		}

		for(int j=0; j<=sz[i]; j++){

			dp[i][j][0] = aux[j][0] + aux[j][1] * 2 + aux[j][2] * 2;

			dp[i][j][1] = aux[j][0] + aux[j][1];

			dp[i][j][0] %= mod;

			dp[i][j][1] %= mod;

		}

		sz[i]++;

	}

	lint ret = 0;

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

		lint cur = dp[1][i][0] * fact[n - i] % mod;

		if(i & 1) cur = mod - cur;

		ret += cur;

	}

	cout << ret % mod << endl;

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

#include<string>

#include<iomanip>

#include<cmath>

#include<vector>

#include<algorithm>



using namespace std;



#define int long long

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

#define INF ((long long)1e18)

#define MOD ((int)1e9+7)

#define endl "\n"



#define yn(f) ((f)?"Yes":"No")

#define YN(f) ((f)?"YES":"NO")



#define MAX 110000



int s[MAX], t[MAX], x[MAX];

pair<int,int> temp[MAX], temp2[MAX], que[MAX];



signed main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	cout<<fixed<<setprecision(10);

	

	int A, B, Q;

	

	cin>>A>>B>>Q;

	

	rep(i,A)cin>>s[i];

	rep(i,B)cin>>t[i];

	rep(i,Q){

		cin>>x[i];

		que[i].first = x[i];

		que[i].second = i;

	}

	

	sort(x,x+Q);

	sort(que,que+Q);

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

		 que[i].first = que[i].second;

		 que[i].second = i;

	}

	sort(que,que+Q);

	for(int i = 0, j = 0; i < Q; i++){

		for(;j < A;j++){

			if(x[i] < s[j]) break;

		}

		if(j == 0) temp[i].first = INF;

		else temp[i].first = x[i]-s[j-1];

		

		if(j == A) temp[i].second = INF;

		else temp[i].second = s[j]-x[i];

		// cout<<i<<" "<<temp[i].first<<" "<<temp[i].second<<endl;

		// cout<<x[i]<<" "<<s[j]<<endl;

	}

	

	for(int i = 0, j = 0; i < Q; i++){

		for(;j < B;j++){

			if(x[i] < t[j]) break;

		}

		if(j == 0) temp2[i].first = INF;

		else temp2[i].first = x[i]-t[j-1];

		

		if(j == B) temp2[i].second = INF;

		else temp2[i].second = t[j]-x[i];

		// cout<<i<<" "<<temp2[i].first<<" "<<temp2[i].second<<endl;

	}

	

	for(int j = 0; j < Q; j++){

		int i = que[j].second;

		cout<<min(min(max(temp[i].first,temp2[i].first),max(temp[i].second,temp2[i].second)),min(min(temp[i].first,temp2[i].second)*2+max(temp[i].first,temp2[i].second),min(temp[i].second,temp2[i].first)*2 + max(temp[i].second,temp2[i].first)))<<endl;

		// cout<<temp[i].first<<" "<<temp[i].second<<endl;

		// cout<<temp2[i].first<<" "<<temp2[i].second<<endl<<endl;;

	}

	

	

	return 0;

}

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

#include<algorithm>



using namespace std;



#define int long long

#define INF ((long long)1e18)

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



#define MAX 110000

	

int s[MAX], t[MAX], ans[MAX];

pair<int,int> x[MAX];



signed main(){



	int A, B, Q, a, b, c, d;

	

	scanf("%lld %lld %lld", &A,&B,&Q);

	

	rep(i,A)scanf("%lld",&s[i]);

	rep(i,B)scanf("%lld",&t[i]);

	rep(i,Q){scanf("%lld",&x[i].first);x[i].second = i;}

	

	sort(x,x+Q);

	

	for(int i = 0, j = 0, k = 0; i < Q; i++){

		for(;j < A && x[i].first >= s[j];j++);

		for(;k < B && x[i].first >= t[k];k++);

		a = j?x[i].first-s[j-1]:INF,b = j-A?s[j]-x[i].first:INF,c = k?x[i].first-t[k-1]:INF,d = k-B?t[k]-x[i].first:INF;

		ans[x[i].second] = min(min(max(a,c),max(b,d)),min(a>d?d*2+a:a*2+d,b>c?c*2+b:b*2+c));

	}

	

	rep(i,Q) printf("%lld\n",ans[i]);

	

	return 0;

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

#include<string>

#include<iomanip>

#include<cmath>

#include<vector>

#include<algorithm>



using namespace std;



#define int long long

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

#define INF ((long long)1e18)

#define MOD ((int)1e9+7)

#define endl "\n"



#define yn(f) ((f)?"Yes":"No")

#define YN(f) ((f)?"YES":"NO")



#define MAX 110000



int s[MAX], t[MAX];

pair<int,int> temp[MAX], temp2[MAX],x[MAX];



signed main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	cout<<fixed<<setprecision(10);

	

	int A, B, Q;

	

	cin>>A>>B>>Q;

	

	rep(i,A)cin>>s[i];

	rep(i,B)cin>>t[i];

	rep(i,Q){

		cin>>x[i].first;

		x[i].second = i;

	}

	

	sort(x,x+Q);

	

	for(int i = 0, j = 0, k = 0; i < Q; i++){

		for(;j < A;j++) if(x[i].first < s[j]) break;

		for(;k < B;k++) if(x[i].first < t[k]) break;

		

		if(j == 0) temp[x[i].second].first = INF;

		else temp[x[i].second].first = x[i].first-s[j-1];

		

		if(j == A) temp[x[i].second].second = INF;

		else temp[x[i].second].second = s[j]-x[i].first;

		

		if(k == 0) temp2[x[i].second].first = INF;

		else temp2[x[i].second].first = x[i].first-t[k-1];

		

		if(k == B) temp2[x[i].second].second = INF;

		else temp2[x[i].second].second = t[k]-x[i].first;

		

	}

	

	for(int i = 0; i < Q; i++) cout<<min(min(max(temp[i].first,temp2[i].first),max(temp[i].second,temp2[i].second)),min(min(temp[i].first,temp2[i].second)*2+max(temp[i].first,temp2[i].second),min(temp[i].second,temp2[i].first)*2 + max(temp[i].second,temp2[i].first)))<<endl;

	

	

	return 0;

}

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

#include<algorithm>



using namespace std;



#define int long long

#define INF ((long long)1e18)

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



#define MAX 110000

	

int s[MAX], t[MAX], ans[MAX];

pair<int,int> x[MAX];



signed main(){



	int A, B, Q, a, b, c, d;

	

	scanf("%lld %lld %lld", &A,&B,&Q);

	

	rep(i,A)scanf("%lld",&s[i]);

	rep(i,B)scanf("%lld",&t[i]);

	rep(i,Q){scanf("%lld",&x[i].first);x[i].second = i;}

	

	sort(x,x+Q);

	

	for(int i = 0, j = 0, k = 0; i < Q; i++){

		for(;j < A && x[i].first >= s[j];j++);

		for(;k < B && x[i].first >= t[k];k++);

		a = j?x[i].first-s[j-1]:INF,b = j-A?s[j]-x[i].first:INF,c = k?x[i].first-t[k-1]:INF,d = k-B?t[k]-x[i].first:INF;

		ans[x[i].second] = min(min(max(a,c),max(b,d)),min(a>d?d*2+a:a*2+d,b>c?c*2+b:b*2+c));

	}

	

	rep(i,Q) printf("%lld\n",ans[i]);

	

	return 0;

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

#include<string>

#include<iomanip>

#include<cmath>

#include<vector>

#include<algorithm>



using namespace std;



#define int long long

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

#define INF ((long long)1e18)

#define MOD ((int)1e9+7)

#define endl "\n"



#define yn(f) ((f)?"Yes":"No")

#define YN(f) ((f)?"YES":"NO")



#define MAX 110000



int s[MAX], t[MAX], ans[MAX];

pair<int,int> x[MAX];



signed main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	// cout<<fixed<<setprecision(10);

	

	int A, B, Q, a, b, c, d;

	

	cin>>A>>B>>Q;

	

	rep(i,A)cin>>s[i];

	rep(i,B)cin>>t[i];

	rep(i,Q){

		cin>>x[i].first;

		x[i].second = i;

	}

	

	sort(x,x+Q);

	

	for(int i = 0, j = 0, k = 0; i < Q; i++){

		for(;j < A && x[i].first >= s[j];j++);

		for(;k < B && x[i].first >= t[k];k++);

		a = j?x[i].first-s[j-1]:INF;

		b = j-A?s[j]-x[i].first:INF;

		c = k?x[i].first-t[k-1]:INF;

		d = k-B?t[k]-x[i].first:INF;

		ans[x[i].second] = min(min(max(a,c),max(b,d)),min(min(a,d)*2+max(a,d),min(b,c)*2 + max(b,c)));

	}

	

	for(int i = 0; i < Q; i++) cout<<ans[i]<<endl;

	

	return 0;

}

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

#include<algorithm>



using namespace std;



#define int long long

#define INF ((long long)1e18)

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



#define MAX 110000

	

int s[MAX], t[MAX], ans[MAX];

pair<int,int> x[MAX];



signed main(){



	int A, B, Q, a, b, c, d;

	

	scanf("%lld %lld %lld", &A,&B,&Q);

	

	rep(i,A)scanf("%lld",&s[i]);

	rep(i,B)scanf("%lld",&t[i]);

	rep(i,Q){scanf("%lld",&x[i].first);x[i].second = i;}

	

	sort(x,x+Q);

	

	for(int i = 0, j = 0, k = 0; i < Q; i++){

		for(;j < A && x[i].first >= s[j];j++);

		for(;k < B && x[i].first >= t[k];k++);

		a = j?x[i].first-s[j-1]:INF,b = j-A?s[j]-x[i].first:INF,c = k?x[i].first-t[k-1]:INF,d = k-B?t[k]-x[i].first:INF;

		ans[x[i].second] = min(min(max(a,c),max(b,d)),min(a>d?d*2+a:a*2+d,b>c?c*2+b:b*2+c));

	}

	

	rep(i,Q) printf("%lld\n",ans[i]);

	

	return 0;

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

#include<algorithm>

#include<cstdio>

using namespace std;

#define maxn 10100



struct N

{

    int n1, n2, cost;

}e[maxn];



int fa[maxn];



bool cmp(N a, N b)

{

    return a.cost<b.cost;

}



void init()

{

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

        fa[i]=i;

}



int find1(int x)

{

    if(x==fa[x])

        return x;

    fa[x]=find1(fa[x]);

    return fa[x];

}



int main()

{

    int n,m;

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

    {

        init();

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

            scanf("%d%d%d",&e[i].n1,&e[i].n2,&e[i].cost);

        sort(e,e+m,cmp);

        int num=0;

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

        {

            int a=find1(e[i].n1);

            int b=find1(e[i].n2);

            if(a==b)

                continue;

            fa[a]=fa[b];

            num++;

            if(num==(n+1)/2)

            {

                cout << e[i].cost << endl;

                break;

            }

        }

    }

}

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

#include <vector>

#include <cstdlib>

#include <algorithm>



using namespace std;



struct edge {

	int u, v, w;

	edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}

	bool operator<(const edge& o) const {

		return w < o.w;

	}

};



int fa[1005];



int root(int x) {

	return fa[x] = (x == fa[x] ? x : root(fa[x]));

}



int n, m;

vector<edge> e;



int main() {

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

		e.clear();

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

			fa[i] = i;

		}

		int u, v, w;

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

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

			e.push_back(edge(u, v, w));

		}

		sort(e.begin(), e.end());

		int cnt = 0;

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

			int fa1 = root(e[i].u);

			int fa2 = root(e[i].v);

			if (fa1 != fa2) {

				fa[fa1] = fa2;

				if (++cnt == (n + 1)/2) {

					printf("%d\n", e[i].w);

					break;

				}

			}

		}

	}

    return 0;

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

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string.h>



using namespace std;



const int MAXN = 200000 + 100;

int n, m;

struct Node

{

    int u, v, w;

}edge[MAXN];

int pre[MAXN];



int finds(int x)

{

    return x == pre[x] ? x : (pre[x] = finds(pre[x]));

}



bool cmp(Node a, Node b)

{

    return a.w < b.w;

}



void solve()

{

    int ans = 0;



    sort(edge, edge + m, cmp);



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

    {

        pre[i] = i;

    }



    int num = 0;



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

    {

        int fa = finds(edge[i].u), fb = finds(edge[i].v);



        if (fa != fb)

        {

            pre[fa] = fb;

            num++;

            if (num == n / 2) ans = edge[i].w;

            if (num == n - 1) break;

        }

    }



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

}



void input()

{

    int u, v, w;



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

    {

        if (n == 0 && m == 0)

        {

            break;

        }

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

        {

            scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);

        }



        solve();

    }

}



int main()

{

    input();

    return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 100000;

struct node{

	int u,v,dist;

}a[MAXN + 10];

int n,m;

int fa[MAXN + 10];

int cnt;

int num[MAXN + 10];

int tot;



bool cmp(const node &x,const node &y){

	return x.dist < y.dist;

}



int find(int x){

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

}



int main(){

	while(scanf("%d%d",&n,&m) == 2 && n && m){

		cnt = 0;

		tot = 0;

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

			int u,v,dist;

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

			a[++cnt].u = u;

			a[cnt].v = v;

			a[cnt].dist = dist;

			a[++cnt].v = u;

			a[cnt].u = v;

			a[cnt].dist = dist;

		}

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

			fa[i] = i;

		sort(a + 1,a + cnt + 1,cmp);

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

			int x = find(a[i].u);

			int y = find(a[i].v);

			if(x == y)

				continue;

			num[++tot] = a[i].dist;

			fa[x] =y;

		}

		printf("%d\n",num[(tot + 1) / 2]);

	}

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

#include<algorithm>

#include<cstdio>

using namespace std;

#define maxn 10100



struct N

{

    int n1, n2, cost;

}e[maxn];



int fa[maxn];



bool cmp(N a, N b)

{

    return a.cost<b.cost;

}



void init()

{

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

        fa[i]=i;

}



int find1(int x)

{

    if(x==fa[x])

        return x;

    fa[x]=find1(fa[x]);

    return fa[x];

}



int main()

{

    int n,m;

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

    {

        init();

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

            scanf("%d%d%d",&e[i].n1,&e[i].n2,&e[i].cost);

        sort(e,e+m,cmp);

        int num=0;

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

        {

            int a=find1(e[i].n1);

            int b=find1(e[i].n2);

            if(a==b)

                continue;

            fa[a]=fa[b];

            num++;

            if(num==(n+1)/2)

            {

                cout << e[i].cost << endl;

                break;

            }

        }

    }

}

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

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 100000;

struct node{

	int u,v,dist;

}a[MAXN + 10];

int n,m;

int fa[MAXN + 10];

int cnt;

int num[MAXN + 10];

int tot;



bool cmp(const node &x,const node &y){

	return x.dist < y.dist;

}



int find(int x){

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

}



int main(){

	while(scanf("%d%d",&n,&m) == 2 && n && m){

		cnt = 0;

		tot = 0;

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

			int u,v,dist;

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

			a[++cnt].u = u;

			a[cnt].v = v;

			a[cnt].dist = dist;

			a[++cnt].v = u;

			a[cnt].u = v;

			a[cnt].dist = dist;

		}

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

			fa[i] = i;

		sort(a + 1,a + cnt + 1,cmp);

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

			int x = find(a[i].u);

			int y = find(a[i].v);

			if(x == y)

				continue;

			num[++tot] = a[i].dist;

			fa[x] =y;

		}

		printf("%d\n",num[(tot + 1) / 2]);

	}

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

#include <vector>

#include <cstdlib>

#include <algorithm>



using namespace std;



struct edge {

	int u, v, w;

	edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}

	bool operator<(const edge& o) const {

		return w < o.w;

	}

};



int fa[1005];



int root(int x) {

	return fa[x] = (x == fa[x] ? x : root(fa[x]));

}



int n, m;

vector<edge> e;



int main() {

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

		e.clear();

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

			fa[i] = i;

		}

		int u, v, w;

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

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

			e.push_back(edge(u, v, w));

		}

		sort(e.begin(), e.end());

		int cnt = 0;

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

			int fa1 = root(e[i].u);

			int fa2 = root(e[i].v);

			if (fa1 != fa2) {

				fa[fa1] = fa2;

				if (++cnt == (n + 1)/2) {

					printf("%d\n", e[i].w);

					break;

				}

			}

		}

	}

    return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 100000;

struct node{

	int u,v,dist;

}a[MAXN + 10];

int n,m;

int fa[MAXN + 10];

int cnt;

int num[MAXN + 10];

int tot;



bool cmp(const node &x,const node &y){

	return x.dist < y.dist;

}



int find(int x){

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

}



int main(){

	while(scanf("%d%d",&n,&m) == 2 && n && m){

		cnt = 0;

		tot = 0;

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

			int u,v,dist;

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

			a[++cnt].u = u;

			a[cnt].v = v;

			a[cnt].dist = dist;

			a[++cnt].v = u;

			a[cnt].u = v;

			a[cnt].dist = dist;

		}

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

			fa[i] = i;

		sort(a + 1,a + cnt + 1,cmp);

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

			int x = find(a[i].u);

			int y = find(a[i].v);

			if(x == y)

				continue;

			num[++tot] = a[i].dist;

			fa[x] =y;

		}

		printf("%d\n",num[(tot + 1) / 2]);

	}

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

#define eps 1e-9

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

#define INS(x) inserter(x,x.begin())

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define MAXN 10005

#define MAXM 40005

#define INF 0x3fffffff

#define PB push_back

#define MP make_pair

#define X first

#define Y second

#define clr(x,y) memset(x,y,sizeof(x));

using namespace std;

typedef long long LL;

int i,j,k,n,m,x,y,T,ans,big,cas,num,len;

bool flag;



int edge,head[MAXN];

struct node

{

	int x,y,w;

}p[10005];



bool cmp(node a,node b)

{

	return a.w<b.w;

}



int pre[10005];   //??根?点，起始??pre[i]=i

int find(int u)   //?找u?点??集合的根?点

{

	int r=u;

	while (pre[r]!=r) r=pre[r];  //沿着?向上不断找father，直到找到根?点root (存入r中)

	int i=u,j;

	while (i!=r)   //路径??，即把向上找???的?个?点（重新沿?点向上找一遍），他?的father都??root

	{

		j=pre[i];

		pre[i]=r;

		i=j;

	}

	return r;  //返回根?点的?号

}



int main()

{

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

	{

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

		edge=0;

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

		{

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

		}

		sort(p,p+m,cmp);

		for (i=1;i<=n;i++) pre[i]=i;

		int t=n/2;num=0;

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

		{

			int fx=find(p[i].x);

			int fy=find(p[i].y);

			if (fx!=fy)

			{

				pre[fx]=fy;

				num++;

				if (num==t)

				{

					printf("%d\n",p[i].w);

					break;

				}

			}

		}

		

	}

	

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 100000;

struct node{

	int u,v,dist;

}a[MAXN + 10];

int n,m;

int fa[MAXN + 10];

int cnt;

int num[MAXN + 10];

int tot;



bool cmp(const node &x,const node &y){

	return x.dist < y.dist;

}



int find(int x){

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

}



int main(){

	while(scanf("%d%d",&n,&m) == 2 && n && m){

		cnt = 0;

		tot = 0;

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

			int u,v,dist;

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

			a[++cnt].u = u;

			a[cnt].v = v;

			a[cnt].dist = dist;

			a[++cnt].v = u;

			a[cnt].u = v;

			a[cnt].dist = dist;

		}

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

			fa[i] = i;

		sort(a + 1,a + cnt + 1,cmp);

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

			int x = find(a[i].u);

			int y = find(a[i].v);

			if(x == y)

				continue;

			num[++tot] = a[i].dist;

			fa[x] =y;

		}

		printf("%d\n",num[(tot + 1) / 2]);

	}

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

using namespace std;

const int MAXN=1005;

const int MAXM=10005;

int fa[MAXN];

pair< int, pair<int, int> > E[MAXM];

int find(int x){

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

}

int main(){

    int n, m;

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

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

            fa[i]=i;

        }

        for(int i=0, x, y, w; i<m; i++){

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

            E[i]=make_pair(w,make_pair(x,y));

        }

        sort(E,E+m);

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

            int u=find(E[i].second.first);

            int v=find(E[i].second.second);

            int w=E[i].first;

            if(u!=v){

                fa[u]=v;

                cnt++;

                if(cnt*2>=n-1){

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

                    break;

                }

            }

        }

    }

    return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 100000;

struct node{

	int u,v,dist;

}a[MAXN + 10];

int n,m;

int fa[MAXN + 10];

int cnt;

int num[MAXN + 10];

int tot;



bool cmp(const node &x,const node &y){

	return x.dist < y.dist;

}



int find(int x){

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

}



int main(){

	while(scanf("%d%d",&n,&m) == 2 && n && m){

		cnt = 0;

		tot = 0;

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

			int u,v,dist;

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

			a[++cnt].u = u;

			a[cnt].v = v;

			a[cnt].dist = dist;

			a[++cnt].v = u;

			a[cnt].u = v;

			a[cnt].dist = dist;

		}

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

			fa[i] = i;

		sort(a + 1,a + cnt + 1,cmp);

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

			int x = find(a[i].u);

			int y = find(a[i].v);

			if(x == y)

				continue;

			num[++tot] = a[i].dist;

			fa[x] =y;

		}

		printf("%d\n",num[(tot + 1) / 2]);

	}

}//