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



using namespace std;

#define pb push_back

#define int long long

int n,m,check=0,c[100005],num[2];

vector<int> graph[100005];

bool vis[100005];

void dfs(int u,int color){

    num[color]++;

    vis[u]=1;

    for(int i=0;i<graph[u].size();i++){

        int v=graph[u][i];

        if(vis[v]==0){

            c[v]=1-color;

            dfs(v,1-color);

        }

    }

}

signed main(){

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

    cin>>n>>m;

    int u,v;

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

        cin>>u>>v;

        graph[u].pb(v);

        graph[v].pb(u);

    }

    c[1]=0;

    dfs(1,0);

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

        for(int j=0;j<graph[i].size();j++){

            int v=graph[i][j];

            if(c[v]==c[i])

                check=1;

        }

    }

    if(check==1)

        cout<<n*(n-1)/2-m;

    else

        cout<<num[0]*num[1]-m;

}


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

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100000 +5;

int n, m, tot, head[maxn], color[maxn];

struct edge {

	int to, nxt;

} G[maxn << 1];



inline void add_edge (int u, int v) {

	tot ++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int x, int now = 0, int fa = 0) {

	color[x] = now, now ^= 1;

    for (int j = head[x]; j; j = G[j].nxt) {

        if (color[G[j].to] == -1) dfs(G[j].to, now, x);

        if (color[G[j].to] != now) {

        	printf ("%lld\n", (long long)n * (n - 1) / 2 - m);

        	exit(0);

		}

    }

}



int main() {

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

	int u, v;

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

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

		add_edge (u, v); add_edge(v, u);

	}

	memset (color, 255, sizeof (color));

	dfs(1);

	int a = 0, b = 0;

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

		if (color[i]) a++;

		else b++;

	}

	printf ("%lld", (long long)a * b - m);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//Trial code here

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

bool f=0;

int c[N],cnt[3];

vector<int>G[N];

void dfs(int x,int ff=1)

{

    if(c[x])

    {

        f|=ff!=c[x];

        return;

    }

    c[x]=ff;

    cnt[ff]++;

    for(int u:G[x])

    dfs(u,3-ff);

}

int main()

{

    int n,m;

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

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

    {

        int u,v;

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

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(1);

    printf("%lld\n",f?1LL*n*(n-1)/2-m:1LL*cnt[1]*cnt[2]-m);

    return 0;

}

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

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100000 +5;

int n, m, tot, head[maxn], color[maxn];

struct edge {

	int to, nxt;

} G[maxn << 1];



inline void add_edge (int u, int v) {

	tot ++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int x, int now = 0, int fa = 0) {

	color[x] = now, now ^= 1;

    for (int j = head[x]; j; j = G[j].nxt) {

        if (color[G[j].to] == -1) dfs(G[j].to, now, x);

        if (color[G[j].to] != now) {

        	printf ("%lld\n", (long long)n * (n - 1) / 2 - m);

        	exit(0);

		}

    }

}



int main() {

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

	int u, v;

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

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

		add_edge (u, v); add_edge(v, u);

	}

	memset (color, 255, sizeof (color));

	dfs(1);

	int a = 0, b = 0;

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

		if (color[i]) a++;

		else b++;

	}

	printf ("%lld", (long long)a * b - m);

	return 0;

}

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

#include<cstdio>

#include<vector> 

#include<cstring>

using namespace std;

const int maxn = 1e5 + 5;

vector<int> list[maxn];

int vis[maxn];

int lose=0;

void bfs(int ne,int be,int re)

{

    if(!lose)

    {

        if(vis[ne]==-1)

            vis[ne]=re;

        else

            if(vis[ne]!=re)

            {

                lose=1;

                return;

            }

            else

                return;

        for(int i=0;i<list[ne].size();i++)

        {

            if(list[ne][i]!=be)

                bfs(list[ne][i],ne,!re);    

        }



    }



}

int main()

{

    long long m,n;

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

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

    {

        int x,y;

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

        list[x].push_back(y);

        list[y].push_back(x);

    }

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

    bfs(1,0,1);

    long long q=0,p=0;

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

    {

        if(vis[i]==1)

            q++;

        else

            p++;

    }

    if(lose)

        printf("%lld\n",m*(m-1)/2-n);

    else

        printf("%lld\n",q*p-n);



    return 0;

}

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

#define maxn 100005

#define ll long long

using namespace std;



int head[maxn],cnt,vis[maxn];ll cnt1,cnt2,n,m;



struct edge{

	int to,nxt;

}e[maxn<<1];



void add(int u,int v){

	e[++cnt]=(edge){v,head[u]};

	head[u]=cnt;

}



void dfs(int u,int fa,int col){

	if(!vis[u]) vis[u]=col;

	else {

		if(vis[u]!=col){

			printf("%lld",(n-1)*n/2-m);

			exit(0);

		}

		return ;

	}

	col&1?cnt1++:cnt2++;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa) continue;

		dfs(v,u,(col&1)+1);

	}

}



int main(){

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

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

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

		add(u,v);add(v,u);

	}

	dfs(1,0,1);

	printf("%lld",cnt1*cnt2-m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#pragma GCC optimize("Ofast")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>



using namespace std;



#define PB push_back

#define MP make_pair

#define EB emplace_back

#define f first

#define s second

#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 FILL(a, b) memset(a, b, sizeof a)

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

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

#define bitc(n) __builtin_popcount(n)

#define MAGIC0 mt19937 rnd(time(0)); //rnd()



typedef long long LL;

typedef unsigned long long ULL;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;



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

const LL LINF = 1LL * INF*INF;

const int MAX = 1e6 + 7;

const double PI = acos(-1.);

const double EPS = 1e-7;

const int MAXN = 100005;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



unordered_map<int, int> mep(200007);



int main()

{

	ios_base::sync_with_stdio(0);

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

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

	time_t st = clock();

	int n;

	cin >> n;

	VI a(n);

	FOR(i, 0, n)

	{

		cin >> a[i];

		mep[a[i]]++;

	}

	

	deque<int> res;

	int ind = rnd() % n;

	res.PB(a[ind]);

	mep[a[ind]]--;

	FOR(i, 0, n)

	{

		if (mep[a[i]] == 0 || !mep.count(a[i] ^ a[ind]) || mep[a[i] ^ a[ind]] == 0)

		{

			continue;

		}

		res.PB(a[i]);

		mep[a[i]]--;

		int it = 0;

		while(true)

		{

			if (((double)clock() - st) / CLOCKS_PER_SEC >= 1.9)

			{

				cout << "No\n";

				return 0;

			}

			++it;

			if (it % 2 == 0)

			{

				int sz = SZ(res);

				int el = res[sz-1] ^ res[sz-2];

				if (mep.count(el) && mep[el] > 0)

				{

					res.PB(el);

					mep[el]--;

				}

				else

				{

					break;

				}

			}

			else

			{

				int el = res[0] ^ res[1];

				if (mep.count(el) && mep[el] > 0)

				{

					res.push_front(el);

					mep[el]--;

				}

				else

				{

					break;

				}

			}

		}

		if (SZ(res) == n)

		{

			cout << "Yes\n";

			return 0;

		}

		while(SZ(res) > 1)

		{

			mep[res.back()]++;

			res.pop_back();

		}

	}

	

	cout << "No\n";

	

	return 0;

}
















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

#include<algorithm>

using namespace std;



int a[100001];

int main(){

	int n;

	scanf("%d",&n);

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

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

	int ql=1;

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

		if(a[i])ql=0;

	if(ql){

		printf("Yes\n");

		return 0;

	}

	if(n%3){

		printf("No\n");

		return 0;

	}

	sort(a+1,a+n+1);

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

		if(i!=n/3+1&&i!=n/3*2+1&&a[i]!=a[i-1]){

			printf("No\n");

			return 0;

		}

	if(a[1]^a[n/3+1]^a[n/3*2+1]){

		printf("No\n");

		return 0;

	}

	printf("Yes\n");

}

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

using namespace std;



int N, ai;

int main(){

	scanf("%d", &N);

	

	map <int, int> mp;

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

		scanf("%d", &ai);

		mp[ai]++;

	}

	

	if(N % 3 == 0){

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

			if(mp.begin()->first == 0)printf("Yes\n");

			else printf("No\n");

		}else if(mp.size() == 2){

			if(mp.begin()->first == 0 && mp.begin()->second * 2 == next(mp.begin())->second)printf("Yes\n");

			else printf("No\n");

		}else if(mp.size() == 3){

			if((mp.begin()->first ^ next(mp.begin())->first ^ next(next(mp.begin()))->first) != 0)printf("No\n");

			else if(mp.begin()->second != next(mp.begin())->second || next(mp.begin())->second != next(next(mp.begin()))->second)printf("No\n");

			else printf("Yes\n");

		}else printf("No\n");

	}else{

		if((int)mp.size() > 1 || mp.begin()->first != 0)printf("No\n");

		else printf("Yes\n");

	}

	

	return 0;

}


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

#include<algorithm>

using namespace std;



int a[100001];

int main(){

	int n;

	scanf("%d",&n);

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

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

	int ql=1;

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

		if(a[i])ql=0;

	if(ql){

		printf("Yes\n");

		return 0;

	}

	if(n%3){

		printf("No\n");

		return 0;

	}

	sort(a+1,a+n+1);

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

		if(i!=n/3+1&&i!=n/3*2+1&&a[i]!=a[i-1]){

			printf("No\n");

			return 0;

		}

	if(a[1]^a[n/3+1]^a[n/3*2+1]){

		printf("No\n");

		return 0;

	}

	printf("Yes\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//https://vjudge.net/contest/342760#problem/A

/*

* Author : MaxSally

*/

/********   All Required Header Files ********/

#include<bits/stdc++.h>

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/

#define SCD(t) scanf("%d",&t)

#define SCLD(t) scanf("%ld",&t)

#define SCLLD(t) scanf("%lld",&t)

#define SCC(t) scanf("%c",&t)

#define SCS(t) scanf("%s",t)

#define SCF(t) scanf("%f",&t)

#define SCLF(t) scanf("%lf",&t)

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

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

#define rrep(i, j, k) for (int i = j; i >= k; --i)

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

#define rall(cont) cont.end(), cont.begin()

#define foreach(i, a) for(auto i: a)

#define forEach(it, l) for (auto it = l.begin(); it != l.end(); it++)

#define in(A, B, C) assert( B <= A && A <= C)

#define mp make_pair

#define pb push_back

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

#define epsi 1e-9

#define PI 3.1415926535897932384626433832795

#define mod 1000000007

#define read(type) readInt<type>()

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

#define ll long long int

#define left tuyiuoi

#define right fgjhk

#define ss second

#define ff first

#define debug(a) cout << #a << ": " << a << endl

#define debuga1(a, l, r) rep(i, l, r) cout << a[i] << " "; cout << endl

#define Flag(n) cout << "here " << n << endl

const double pi=acos(-1.0);

typedef pair<int, int> pii;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef vector<vl> vll;

typedef pair<ll, ll> pll;

typedef vector<string> vs;

typedef vector<pii> vii;

typedef vector<pll> vpll;

typedef vector<vi> vvi;

typedef map<int,int> MPII;

typedef set<int> SETI;

typedef multiset<int> MSETI;

typedef long int int32;

typedef unsigned long int uint32;

typedef long long int int64;

typedef unsigned long long int  uint64;



const int N = 100005;

int n, a[N];



int main(){

    io;

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

    cin >> n;

    int totalSum = 0;

    rep(i, 1, n){

        cin >> a[i];

        totalSum ^= a[i];

    }

    cout << (totalSum == 0? "Yes": "No");



    return 0;

}




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

#include<algorithm>

using namespace std;



int a[100001];

int main(){

	int n;

	scanf("%d",&n);

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

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

	int ql=1;

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

		if(a[i])ql=0;

	if(ql){

		printf("Yes\n");

		return 0;

	}

	if(n%3){

		printf("No\n");

		return 0;

	}

	sort(a+1,a+n+1);

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

		if(i!=n/3+1&&i!=n/3*2+1&&a[i]!=a[i-1]){

			printf("No\n");

			return 0;

		}

	if(a[1]^a[n/3+1]^a[n/3*2+1]){

		printf("No\n");

		return 0;

	}

	printf("Yes\n");

}

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



using namespace std;



int main()



{

    long long int n,sum=0,a;

    cin>>n;

    while(n--)

    {

        cin>>a;

        sum=sum^a;

}

    if(sum==0)

    cout<<"Yes"<<endl;

    else

cout<<"No"<<endl;

    

}

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

#include<algorithm>

using namespace std;



int a[100001];

int main(){

	int n;

	scanf("%d",&n);

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

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

	int ql=1;

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

		if(a[i])ql=0;

	if(ql){

		printf("Yes\n");

		return 0;

	}

	if(n%3){

		printf("No\n");

		return 0;

	}

	sort(a+1,a+n+1);

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

		if(i!=n/3+1&&i!=n/3*2+1&&a[i]!=a[i-1]){

			printf("No\n");

			return 0;

		}

	if(a[1]^a[n/3+1]^a[n/3*2+1]){

		printf("No\n");

		return 0;

	}

	printf("Yes\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#pragma GCC optimize("Ofast")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>



using namespace std;



#define PB push_back

#define MP make_pair

#define EB emplace_back

#define f first

#define s second

#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 FILL(a, b) memset(a, b, sizeof a)

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

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

#define bitc(n) __builtin_popcount(n)

#define MAGIC0 mt19937 rnd(time(0)); //rnd()



typedef long long LL;

typedef unsigned long long ULL;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;



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

const LL LINF = 1LL * INF*INF;

const int MAX = 1e6 + 7;

const double PI = acos(-1.);

const double EPS = 1e-7;

const int MAXN = 100005;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



set<int> x[100005];

int cnt[100005];



int main()

{

	ios_base::sync_with_stdio(0);

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

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

	int n;

	cin >> n;

	VI a(n);

	FOR(i, 0, n)

	{

		cin >> a[i];

	}

	sort(ALL(a));

	

	if (n % 3 != 0)

	{

		if (a[0] == a[n - 1])

		{

			cout << "Yes\n";

		}

		else

		{

			cout << "No\n";

		}

	}

	else

	if (a[0] == a[n / 3 - 1] && a[n / 3] == a[2 * n / 3 - 1] && a[2 * n / 3] == a[n - 1] && ((a[0] ^ a[n / 3] ^ a[2*n/3]) == 0))

	{

		cout << "Yes\n";

	}

	else

	{

		cout << "No\n";

	}

	

	return 0;

}
















// Optimized solution to the same problem (faster):
//#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;

const double eps = 1e-8;

int n,x;

int main()

{

    scanf("%d", &n);

    int ans = 0;

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

        scanf("%d", &x), ans ^= x;

    if (ans)

        puts("No");

    else

        puts("Yes");

    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





int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N; cin >> N;

    multiset<int> st;

    int a[100010];

    set<int> st2;

    rep(i, N) {

        cin >> a[i];

        st.insert(a[i]);

        st2.insert(a[i]);

    }

    if (st2.size() > 3) {

        cout << "No" << endl;

        return 0;

    }

    int num0 = a[0];

    int num1 = a[1];

    if (st2.size() > 1) {

        auto itr = st2.begin();

        num0 = *itr;

        itr++;

        num1 = *itr;

    }

    int s = num0;

    //dump(num0);

    //dump(num1);

    int t = num0 ^ num1;

    st.erase(st.find(num0));

    st.erase(st.find(num1));

    rep(i, N - 1) {

        if (i == N - 2) {

            if (t != s) {

                cout << "No" << endl;

                return 0;

            }

            break;

        }

        auto itr = st.find(t);

        if (itr == st.end()) {

            cout << "No" << endl;

            return 0;

        }

        

        st.erase(itr);

        num0 = num1;

        num1 = t;

        t = num0 ^ num1;

        //cout << t << endl;

    }

    cout << "Yes" << endl;



    return 0;

}


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

#include<algorithm>

#include<functional>

#include<cmath>

using namespace std;

long long  mod = 1000000007;

long long a[100000];

int main()

{

	int N;

	int count = 1;

	scanf("%d", &N);

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

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

	}

	sort(a, a + N);

	long long number = a[0];

	long long bit;

	int count0 = 1;

	int count1 = 0;

	int count2 = 0;

	if (N % 3 == 0) {

		if (a[0] == 0) {

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

				if (a[i] == 0) {

					count0++;

				}

				if (a[i] != number) {

					number = a[i];

					count++;

				}

			}

			if (count == 2 && count0 == N / 3) {

				printf("Yes");

				return 0;

			}

		}

		else {

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

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

					count0++;

				}

				if (a[i] == a[N / 3]) {

					count1++;

				}

				if (a[i] == a[N / 3 * 2]) {

					count2++;

				}

				if (a[i] != number) {

					number = a[i];

					count++;

				}

			}

			if (count == 3 && count0 == N / 3 && count1 == N / 3 && count2 == N / 3) {

				bit = a[0] ^ a[N / 3];

				if (bit == a[N / 3 * 2]) {

					printf("Yes");

					return 0;

				}

			}

		}

	}

	count0 = 0;

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

		if (a[i] == 0) {

			count0++;

		}

	}

	if (count0 == N) {

		printf("Yes");

	}

	else {

		printf("No");

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// -----------------------------------

// Author     : MatsuTaku

// Country    : Japan

// Created    : 04/26/20 20:17:32

// -----------------------------------



#include <bits/stdc++.h>



using namespace std;

using ll = long long;



int main() {

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



  ll n,m,s; cin>>n>>m>>s;

  struct Train {

    ll s, c, d;

    Train(ll s,ll c,ll d):s(s),c(c),d(d){}

    bool operator>(const Train& x) const {return d>x.d;}

  };

  vector<Train> graph[n];

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

    ll u,v,a,b; cin>>u>>v>>a>>b; u--; v--;

    graph[u].emplace_back(v,a,b);

    graph[v].emplace_back(u,a,b);

  }

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

    int c,d; cin>>c>>d;

    graph[i].emplace_back(i,-c,d);

  }

  constexpr ll MAX = 2500;

  constexpr ll INF = 1e18;

  vector<array<ll, MAX+1>> dp(n);

  for (auto& arr:dp) arr.fill(INF);

  dp[0][min(s,MAX)] = 0;

  priority_queue<Train, vector<Train>, greater<>> qs;

  qs.emplace(0,s,0);

  while (not qs.empty()) {

    auto [s,c,d] = qs.top(); qs.pop();

    if (d > dp[s][min(c,MAX)]) continue;

    for (auto t:graph[s]) {

      if (c-t.c<0) continue;

      if (d+t.d >= dp[t.s][min(c-t.c,MAX)]) continue;

      dp[t.s][min(c-t.c,MAX)] = d+t.d;

      qs.emplace(t.s, c-t.c, d+t.d);

    }

  }

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

    cout << *min_element(dp[i].begin(), dp[i].end()) << endl;

  }



  return 0;

}


// Optimized solution to the same problem (faster):
// -----------------------------------

// Author     : MatsuTaku

// Country    : Japan

// Created    : 04/26/20 20:17:32

// -----------------------------------



#include <bits/stdc++.h>



using namespace std;

using ll = long long;



int main() {

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



  ll n,m,s; cin>>n>>m>>s;

  struct Train {

    ll s, c, d;

    Train(ll s,ll c,ll d):s(s),c(c),d(d){}

    bool operator>(const Train& x) const {return d>x.d;}

  };

  vector<Train> graph[n];

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

    ll u,v,a,b; cin>>u>>v>>a>>b; u--; v--;

    graph[u].emplace_back(v,a,b);

    graph[v].emplace_back(u,a,b);

  }

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

    int c,d; cin>>c>>d;

    graph[i].emplace_back(i,-c,d);

  }

  constexpr ll MAX = 200;

  constexpr ll INF = 1e18;

  vector<array<ll, MAX+1>> dp(n);

  for (auto& arr:dp) arr.fill(INF);

  dp[0][min(s,MAX)] = 0;

  priority_queue<Train, vector<Train>, greater<>> qs;

  qs.emplace(0,s,0);

  while (not qs.empty()) {

    auto [s,c,d] = qs.top(); qs.pop();

    if (d > dp[s][min(c,MAX)]) continue;

    for (auto t:graph[s]) {

      if (c-t.c<0) continue;

      if (d+t.d >= dp[t.s][min(c-t.c,MAX)]) continue;

      dp[t.s][min(c-t.c,MAX)] = d+t.d;

      qs.emplace(t.s, c-t.c, d+t.d);

    }

  }

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

    cout << *min_element(dp[i].begin(), dp[i].end()) << endl;

  }



  return 0;

}


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

using namespace std;

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

typedef pair<ll,ll> pll;

const ll mod=1e9+7;

//const ll mod=998244353;

const ll inf=5e18;



struct E{ll to,co,ti;};

struct P{ll ti,id,re;};

bool operator <(const P &a,const P &b) {return a.ti>b.ti;}

ll dp[50][5001],c[50],d[50],ans[50],n,m,s;

vector<E> edge[50];

priority_queue<P> que;



int main() {

  cin >> n >> m >> s;

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

    ll u,v,a,b;

    cin >> u >> v >> a >> b;

    u--;v--;

    edge[u].push_back({v,a,b});

    edge[v].push_back({u,a,b});

  }

  for(ll i=0;i<n;i++) cin >> c[i] >> d[i];

  que.push({1,0,min(5000LL,s)});

  while(que.size()) {

    P p=que.top();

    que.pop();

    if(dp[p.id][p.re])continue;

    dp[p.id][p.re]=p.ti;

    if(!ans[p.id])ans[p.id]=p.ti;

    for(E q:edge[p.id]) {

      if(p.re>=q.co&&!dp[q.to][p.re-q.co]) {

        que.push({p.ti+q.ti,q.to,p.re-q.co});

      }

    }

    if(p.re+c[p.id]<=5000) que.push({p.ti+d[p.id],p.id,p.re+c[p.id]});

  }

  for(ll i=1;i<n;i++) cout << --ans[i] << endl;

}

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

using namespace std;

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

typedef pair<ll,ll> pll;

const ll mod=1e9+7;

//const ll mod=998244353;

const ll inf=1LL<<61;



typedef pair<ll,pll> ppll;



int main() {

  ll n,m,s;

  cin >> n >> m >> s;

  vector<map<ll,pll>> G(n);

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

    ll u,v,a,b;

    cin >> u >> v >> a >> b;

    u--,v--;

    G[u][v]={a,b};

    G[v][u]={a,b};

  }

  vec mai(n),mnu(n);

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

    cin >> mai[i] >> mnu[i];

  }

  mat d(n,vec(50*(n-1)+1,-1));

  vec ans(n,-1);

  vec mins(n,-1);

  priority_queue<ppll,vector<ppll>,greater<ppll>> q;

  s=min(s,50*(n-1));

  q.push({0,{0,s}});

  while(q.size()) {

    ll td=q.top().first;

    ll f=q.top().second.first;

    ll s=q.top().second.second;

    q.pop();

    ll flag=0;

    if(ans[f]<0) ans[f]=td;

    if(d[f][s]>-1) continue;

    d[f][s]=td;

    mins[f]=s;

    for(auto p:G[f]) {

      ll t=p.first;

      ll co=p.second.first;

      ll v=p.second.second;

      if(s-co>=0&&d[t][s-co]==-1) {

        q.push({td+v,{t,s-co}});

      }

    }

    ll ns=min(s+mai[f],50*(n-1));

    ll nd=td+mnu[f];

    if(d[f][ns]==-1) q.push({nd,{f,ns}});

  }

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

    cout << ans[i] << endl;

  }

}

// Fastest known solution for this problem: