stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<string>

#include<algorithm>

#define P 1000000007

#define MAX 100005

using namespace std;

 

int main(){

  string s;

  long long a[MAX], c[MAX], q[MAX];

  a[0] = 0; c[0] = 0; q[0] = 0;

  long long ans0 = 0, ans1 = 0, ans2 = 0, ans3 = 0, ans = 0;

  long long power = 1;

  cin >> s;

  

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

    a[i+1] = a[i] + ((s[i] == 'A') ? 1 : 0);

    c[i+1] = c[i] + ((s[i] == 'C') ? 1 : 0);

    q[i+1] = q[i] + ((s[i] == '?') ? 1 : 0);

  }

  

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

    if(s[i] == 'B'){

      ans0 += a[i] * (c[s.size()] - c[i+1]);

      ans1 += q[i] * (c[s.size()] - c[i+1]) + a[i] * (q[s.size()] - q[i+1]);

      ans2 += q[i] * (q[s.size()] - q[i+1]);

    }

    if(s[i] == '?'){

      ans1 += a[i] * (c[s.size()] - c[i+1]);

      ans2 += q[i] * (c[s.size()] - c[i+1]) + a[i] * (q[s.size()] - q[i+1]);

      ans3 += q[i] * (q[s.size()] - q[i+1]);

    }

  }

  ans0 %= P; ans1 %= P; ans2 %= P; ans3 %= P;

  

  if(q[s.size()] >= 3){

    for(int i = 0; i < q[s.size()]-3; ++i)

      power = power * 3 % P;

    ans = (ans0 * 27 + ans1 * 9 + ans2 * 3 + ans3)%P*power%P;

  }else if(q[s.size()] == 2){

    ans = (ans0 * 9 + ans1 * 3 + ans2) % P;

  }else if(q[s.size()] == 1){

    ans = (ans0 * 3 + ans1) % P;

  }else if(q[s.size()] == 0){

    ans = ans0;

  }

  cout << ans << endl;

}


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

long long a[4] = {1};

char c;

int main(){

	while(EOF != scanf("%c", &c)) for(int j = 3; j >= 0; j--)

		a[j] = (a[j]*(c-'?'?1:3) + (j&&!(c-'?'&&c-'A'-j+1)?a[j-1]:0))%1000000007;

	printf("%lld\n", a[3]);

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

#include<string>

#define P 1000000007

using namespace std;

 

int main(){

  string s;

  long long a[4] = {1, 0, 0, 0};

  cin >> s;

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

    if(s[i] == '?'){

      a[3] = (a[2] + a[3] * 3) % P;

      a[2] = (a[1] + a[2] * 3) % P;

      a[1] = (a[0] + a[1] * 3) % P;

      a[0] = a[0] * 3 % P; 

    }else if(s[i] == 'A'){

      a[1] = (a[1] + a[0]) % P;

    }else if(s[i] == 'B'){

      a[2] = (a[2] + a[1]) % P;

    }else if(s[i] == 'C'){

      a[3] = (a[3] + a[2]) % P;

    }

  }

  cout << a[3] << endl;

}

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

long long a[4] = {1};

char c;

int main(){

	while(EOF != scanf("%c", &c)) for(int j = 3; j >= 0; j--)

		a[j] = (a[j]*(c-'?'?1:3) + (j&&!(c-'?'&&c-'A'-j+1)?a[j-1]:0))%1000000007;

	printf("%lld\n", a[3]);

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

#define md 1000000007



long long a[4] = {1};

char s[100005];

int main(){

	scanf("%s", s);

	for(int i = 0; s[i] != '\0'; i++) for(int j = 3; j >= 0; j--)

		a[j] = (a[j]*(s[i]=='?'?3:1) + (j&&(s[i]=='?'||s[i]-'A'==j-1)?a[j-1]:0))%md;

	printf("%lld\n", a[3]);

}


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

long long a[4] = {1};

char c;

int main(){

	while(EOF != scanf("%c", &c)) for(int j = 3; j >= 0; j--)

		a[j] = (a[j]*(c-'?'?1:3) + (j&&!(c-'?'&&c-'A'-j+1)?a[j-1]:0))%1000000007;

	printf("%lld\n", a[3]);

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

#include <stdlib.h>

#include <string.h>



#define MAX_LEN (100000)

#define NUM_MOD (1000000007L)



int main() {

  // read inputs

  int N;

  char cs[MAX_LEN + 1];

  scanf("%s", cs);

  N = strlen(cs);



  // calculate powers of 3

  long pow3s[MAX_LEN + 1] = {};

  pow3s[0] = 1;

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

    pow3s[i + 1] = 3 * pow3s[i] % NUM_MOD;

  }



  // solve

  long cnts[3][4] = {}, cntQ = 0;

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

    switch (cs[i]) {

      case 'A':

        cnts[0][0] = (cnts[0][0] + 1) % NUM_MOD;

        break;

      case 'B':

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

          cnts[1][j] = (cnts[1][j] + cnts[0][j]) % NUM_MOD;

        }

        break;

      case 'C':

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

          cnts[2][j] = (cnts[2][j] + cnts[1][j]) % NUM_MOD;

        }

        break;

      case '?':

        cntQ++;

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

          cnts[2][j] = (cnts[2][j] + cnts[1][j - 1]) % NUM_MOD;

        }

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

          cnts[1][j] = (cnts[1][j] + cnts[0][j - 1]) % NUM_MOD;

        }

        cnts[0][1] = (cnts[0][1] + 1) % NUM_MOD;

        break;

    }

  }



  long ans = 0;

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

    ans = (ans + pow3s[cntQ - j] * cnts[2][j]) % NUM_MOD;

  }

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

}

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

#include <stdlib.h>

#include <string.h>



#define MAX_LEN (100000)

#define NUM_MOD (1000000007L)



int main() {

  // read inputs

  int N;

  char cs[MAX_LEN + 1];

  scanf("%s", cs);

  N = strlen(cs);



  // solve

  long cnt = 1, cntA = 0, cntAB = 0, cntABC = 0;

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

    switch (cs[i]) {

      case 'A':

        cntA = (cntA + cnt) % NUM_MOD;

        break;

      case 'B':

        cntAB = (cntAB + cntA) % NUM_MOD;

        break;

      case 'C':

        cntABC = (cntABC + cntAB) % NUM_MOD;

        break;

      case '?':

        cntABC = (3 * cntABC + cntAB) % NUM_MOD;

        cntAB = (3 * cntAB + cntA) % NUM_MOD;

        cntA = (3 * cntA + cnt) % NUM_MOD;

        cnt = 3 * cnt % NUM_MOD;

        break;

    }

  }

  printf("%ld\n", cntABC);

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

#include <stdlib.h>

#include <string.h>



#define MAX_LEN (100000)

#define NUM_MOD (1000000007L)



int main() {

  // read inputs

  int N;

  char cs[MAX_LEN + 1];

  scanf("%s", cs);

  N = strlen(cs);



  // solve

  long dpss[MAX_LEN + 1][4] = {};

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

    dpss[i][0] = 1;

  }

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

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

      dpss[i + 1][j] = dpss[i][j];

    }

    switch (cs[i]) {

      case 'A':

        dpss[i + 1][1] = (dpss[i][1] + dpss[i][0]) % NUM_MOD;

        break;

      case 'B':

        dpss[i + 1][2] = (dpss[i][2] + dpss[i][1]) % NUM_MOD;

        break;

      case 'C':

        dpss[i + 1][3] = (dpss[i][3] + dpss[i][2]) % NUM_MOD;

        break;

      case '?':

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

          dpss[i + 1][j] =

              (3 * dpss[i][j] + (j > 0 ? dpss[i][j - 1] : 0)) % NUM_MOD;

        }

        break;

    }

    // printf("i = %d, c = %c\n", i, cs[i]);

    // for (int j = 0; j < 4; j++) {

    //   printf("%ld ", dpss[i + 1][j]);

    // }

    // printf("\n");

  }

  printf("%ld\n", dpss[N][3]);

}

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

#include <stdlib.h>

#include <string.h>



#define MAX_LEN (100000)

#define NUM_MOD (1000000007L)



int main() {

  // read inputs

  int N;

  char cs[MAX_LEN + 1];

  scanf("%s", cs);

  N = strlen(cs);



  // solve

  long cnt = 1, cntA = 0, cntAB = 0, cntABC = 0;

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

    switch (cs[i]) {

      case 'A':

        cntA = (cntA + cnt) % NUM_MOD;

        break;

      case 'B':

        cntAB = (cntAB + cntA) % NUM_MOD;

        break;

      case 'C':

        cntABC = (cntABC + cntAB) % NUM_MOD;

        break;

      case '?':

        cntABC = (3 * cntABC + cntAB) % NUM_MOD;

        cntAB = (3 * cntAB + cntA) % NUM_MOD;

        cntA = (3 * cntA + cnt) % NUM_MOD;

        cnt = 3 * cnt % NUM_MOD;

        break;

    }

  }

  printf("%ld\n", cntABC);

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

#include <string>

using namespace std;

typedef long long ll;



const ll MOD = 1000000007;



ll modpow(ll x, ll n){

    ll res = 1;

    while(n > 0){

        if(n % 2){

            res = (res * x) % MOD;

        }

        x = (x * x) % MOD;

        n /= 2;

    }

    return res;

}

    



int main()

{

    string s;

    cin >> s;

    ll q = 0;

    ll sa = 0;

    ll sc = 0;

    ll n = s.size();

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

        if(s[i] == '?'){

            q++;

        }

        if(s[i] == 'A'){

            sa++;

        }

        if(s[i] == 'C'){

            sc++;

        }

    }

    ll a[100001] {0};

    ll c[100001] {sc};

    ll lq[100001] {0};

    ll rq[100001] {q};

    if(s[0] == 'C'){

        c[0] = sc - 1;

    }

    if(s[0] == '?'){

        rq[0] = q - 1;

    }

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

        a[i] = a[i - 1];

        if(s[i - 1] == 'A'){

            a[i]++;

        }

        lq[i] = lq[i - 1];

        if(s[i - 1] == '?'){

            lq[i]++;

        }

        c[i] = c[i - 1];

        if(s[i] == 'C'){

            c[i]--;

        }

        rq[i] = rq[i - 1];

        if(s[i] == '?'){

            rq[i]--;

        }

    }

    ll ans = 0;

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

        ll ansi = 0;

        if(s[i] == 'B'){

            ansi = ((a[i] * c[i]) % MOD) * modpow(3, q) + ((lq[i] * c[i]) % MOD) * modpow(3, q - 1) + ((a[i] * rq[i]) % MOD) * modpow(3, q - 1) + ((lq[i] * rq[i]) % MOD) * modpow(3, q - 2);

        }

        if(s[i] == '?'){

            ansi = ((a[i] * c[i]) % MOD) * modpow(3, q - 1) + ((lq[i] * c[i]) % MOD) * modpow(3, q - 2) + ((a[i] * rq[i]) % MOD) * modpow(3, q - 2) + ((lq[i] * rq[i]) % MOD) * modpow(3, q - 3);

        }

        ans = (ans + ansi) % MOD;

    }

    cout << ans << endl;

}

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

#include <string>

using namespace std;

typedef long long ll;



const ll MOD = 1000000007;



int main()

{

    string s;

    cin >> s;

    int n = s.size();

    ll a = 0, b = 0, c = 0;

    ll p = 1;

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

        if(s[i] == 'A') a = (a + p) % MOD;

        if(s[i] == 'B') b = (b + a) % MOD;

        if(s[i] == 'C') c = (c + b) % MOD;

        if(s[i] == '?'){

            c = (c * 3 + b) % MOD;

            b = (b * 3 + a) % MOD;

            a = (a * 3 + p) % MOD;

            p = p * 3 % MOD;

        }

    }

    cout << c << endl;

}
// Slower C++ solution:
/*

Problem Source : agc-034F

Author : oier_hzy

Time : Nov 24 2019

*/



/*



*/



#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



template <typename _tp> inline void cmin(_tp&x, const _tp y) {if(x > y) x = y;}



const ll oo = 0x3f3f3f3f3f3f3f3f;

const int N = 5001;

int a[N];

ll f[N], g[N];

int n, A, B;



int main() {

	scanf("%d%d%d", &n, &A, &B);

	for(int i = 1; i <= n; ++ i) scanf("%d", a+i);

	

	for(int i = 0; i <= n; ++ i) f[i] = g[i] = +oo;

	f[0] = 0;

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

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

			cmin(g[j], f[j] + A);

			cmin(g[a[i]], f[j]);

		}

		for(int j = a[i]; j <= n; ++ j)

			cmin(g[j], f[j] + B);

		for(int j = 0; j <= n; ++ j) f[j] = g[j], g[j] = +oo;

	}

	

	ll Ans = +oo;

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

		cmin(Ans, f[i]);

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.135052233654642x):
/*

Problem Source : agc-032D

Author : oier_hzy

Time : Nov 24 2019

*/



/*

A : move a element to the right

B : ... left



In the best case, there're several fixed elements

We could consider all the circumstances during DP procession



f[i][j] : the first i elements (by coordinate) has been considered, and the last fixed coordinate is j

*/



#include <cstdio>

typedef long long ll;



template <typename _tp> inline void cmin(_tp&x, const _tp y) {if(x > y) x = y;}



const ll oo = 0x3f3f3f3f3f3f3f3f;

const int N = 5001;

int a[N];

ll f[N], g[N];

int n, A, B;



int main() {

	scanf("%d%d%d", &n, &A, &B);

	for(int i = 1; i <= n; ++ i) scanf("%d", a+i);

	

	for(int i = 0; i <= n; ++ i) f[i] = g[i] = +oo;

	f[0] = 0;

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

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

			cmin(g[j], f[j] + A);

			cmin(g[a[i]], f[j]);

		}

		for(int j = a[i]; j <= n; ++ j)

			cmin(g[j], f[j] + B);

		for(int j = 0; j <= n; ++ j) f[j] = g[j], g[j] = +oo;

	}

	

	ll Ans = +oo;

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

		cmin(Ans, f[i]);

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

	return 0;

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

#include <iostream>



#pragma warning(disable : 4996)



using namespace std;



int H, W, N, r[1000][1000], dp[1001][1001];



int main()

{

	while (true)

	{

		scanf("%d", &H);

		scanf("%d", &W);

		scanf("%d", &N);



		if (H == 0 && W == 0 && N == 0) { break; }



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

		{

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

			{

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

			}

		}



		memset(dp, 0, sizeof(dp));



		dp[0][0] = N;



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

		{

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

			{

				if (dp[i][j] % 2 == 0)

				{

					dp[i + 1][j] += dp[i][j] / 2;

					dp[i][j + 1] += dp[i][j] / 2;

				}

				else

				{

					if (r[i][j] == 0)

					{

						dp[i + 1][j] += dp[i][j] / 2 + 1;

						dp[i][j + 1] += dp[i][j] / 2;

					}

					else

					{

						dp[i + 1][j] += dp[i][j] / 2;

						dp[i][j + 1] += dp[i][j] / 2 + 1;

					}

				}

			}

		}



		int x = 0, y = 0;



		while (x != W && y != H)

		{

			int dir = (r[y][x] + dp[y][x] + 1) % 2;



			if (dir == 0)

			{

				y++;

			}

			else

			{

				x++;

			}

		}



		printf("%d %d\n", y + 1, x + 1); // 1 - indexed

	}



	return 0;

}

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

#pragma warning(disable : 4996)

int H, W, T, a[1009][1009], dp[1009][1009];

int main() {

	while (scanf("%d%d%d", &H, &W, &T), H) {

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

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

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

			}

		}

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

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

				dp[i][j] = 0;

			}

		}

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

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

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

				dp[i + 1][j] += (dp[i][j] - a[i][j] + 1) >> 1;

				dp[i][j + 1] += (dp[i][j] + a[i][j]) >> 1;

			}

		}

		int cx = 0, cy = 0;

		while (cx < H && cy < W) {

			if ((dp[cx][cy] ^ a[cx][cy]) & 1) cy++;

			else cx++;

			T >>= 1;

		}

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

	}

	return 0;

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

#include <iostream>



#pragma warning(disable : 4996)



using namespace std;



int H, W, N, r[1000][1000], dp[1001][1001];



int main()

{

	while (true)

	{

		scanf("%d", &H);

		scanf("%d", &W);

		scanf("%d", &N);



		if (H == 0 && W == 0 && N == 0) { break; }



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

		{

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

			{

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

			}

		}



		memset(dp, 0, sizeof(dp));



		dp[0][0] = N;



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

		{

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

			{

				if (dp[i][j] % 2 == 0)

				{

					dp[i + 1][j] += dp[i][j] / 2;

					dp[i][j + 1] += dp[i][j] / 2;

				}

				else

				{

					if (r[i][j] == 0)

					{

						dp[i + 1][j] += dp[i][j] / 2 + 1;

						dp[i][j + 1] += dp[i][j] / 2;

					}

					else

					{

						dp[i + 1][j] += dp[i][j] / 2;

						dp[i][j + 1] += dp[i][j] / 2 + 1;

					}

				}

			}

		}



		int x = 0, y = 0;



		while (x != W && y != H)

		{

			int dir = (r[y][x] + dp[y][x] + 1) % 2;



			if (dir == 0)

			{

				y++;

			}

			else

			{

				x++;

			}

		}



		printf("%d %d\n", y + 1, x + 1); // 1 - indexed

	}



	return 0;

}

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

int H, W, T, a[1009][1009], dp[1009][1009];

int main() {

	while (scanf("%d%d%d", &H, &W, &T), H) {

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

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

				if(i < H && j < W) scanf("%d", &a[i][j]);

				dp[i][j] = 0;

			}

		}

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

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

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

				dp[i + 1][j] += (dp[i][j] - a[i][j] + 1) >> 1;

				dp[i][j + 1] += (dp[i][j] + a[i][j]) >> 1;

			}

		}

		int cx = 0, cy = 0;

		while (cx < H && cy < W) {

			if ((dp[cx][cy] ^ a[cx][cy]) & 1) cy++;

			else cx++;

			T >>= 1;

		}

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

	}

	return 0;

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

#define mod 1000000007

#define f first

#define mt make_tuple

#define s second

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

#define pb push_back

#define eps 1e-7

#define endl "\n"

#define ll long long int

#define mp make_pair

#define p_q priority queue



using namespace std;

     



     int a[100005];

int vis[100005]={0};

 vector< int > adj[100005];



    

// int power(int x, unsigned int y) 

// { 

//     int temp; 

//     if( y == 0) 

//         return 1; 

//     temp = power(x, y/2); 

//     if (y%2 == 0) 

//         return temp*temp; 

//     else

//         return x*temp*temp; 

// } 

     



bool vowl(char c)

{

  return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';

}

 

ll power(ll x, ll y, ll p) 

{ 

    ll res = 1;    

    x = x % p;  

    while (y > 0) 

    { 

        if (y & 1) 

            res = (res*x) % p; 

        y = y>>1;  

        x = (x*x) % p; 

    } 

    return res; 

} 

bool check(ll n, ll p) 

{ 

    if (power(n, (p-1)/2, p) == 1) 

       return true; 

  

    return false; 

} 



int dfs(int source,int vertex_covered)

{

  vis[source]=1;

  if(adj[source].size()==1)

  {

    int v=adj[source][0];

    if(vis[v])

    {

      a[source]=1; 

      return 1;// means i cannot remove that edge

    }

  }



  for(int j=0;j<adj[source].size();j++)

  {

    if(!vis[adj[source][j]])

    {

      vertex_covered+=dfs(adj[source][j],1);

    }

  }

  //cout<<source<<"--->"<< vertex_covered<<endl;

   

   a[source]= vertex_covered;

   return vertex_covered;



    



}

 

 

int main()

{

    fast;

    int t=1;

   // cin>>t;

    while(t--)

    {

      int n;

      cin>>n;

      int a,b,c1=0,c2=0,c3=0;

      cin>>a>>b;

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

      {

        int x;

        cin>>x;

        if(x<=a)

        {

          c1++;

        }

        else if(x>=a+1 && x<=b)

        {

          c2++;

        }

        else if(x>=b+1)

        {

          c3++;

        }

      }

      int ans=min(min(c1,c2),c3);

      cout<<ans<<endl;

      

    }









    return 0;  

}

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

using namespace std;



int a[100500];



int main(){

	int n, b, c, sum = 0, m = 0, l = 0, k = 0;

	cin >> n >> b >> c;

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

		cin >> a[i];

	}

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

		if (a[i] <= b){

			m++;

		}

		else if (a[i] > b && a[i] <= c){

			l++;

		}

		else if(a[i] > c){

			k++;

		}

	}

	

	cout << min(m, min(k, l));

    return 0;

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

using namespace std;

#define inf 1e9

#define ll long long

#define ull unsigned long long

#define M 1000000007

#define P pair<int,int>

#define FOR(i,m,n) for(int i=m;i<n;i++)

#define rep(i,n) FOR(i,0,n)

const int vx[4] = {0,1,0,-1};

const int vy[4] = {1,0,-1,0};

#define PI 3.14159265



int n,m;

vector<int> v[100010];

int a[100010];





int root(int x){

  if(a[x]==x) return x;



  return a[x] = root(a[x]);

}





void unite(int x,int y){

  x = root(x);

  y = root(y);

  if(x==y) return;

  a[x]=a[y];

}



bool find(){

  FOR(i,1,n){

    if(root(i)!=root(i+1)) return false;

  }



  return true;

}



int main(){

  cin>>n>>m;

  rep(i,n+1){

    a[i]=i;

  }

  rep(i,n){

    int k;

    cin>>k;

    rep(j,k){

      int l;

      cin>>l;

      v[l].push_back(i+1);

    }

  }

  rep(i,m+1){

    rep(j,v[i].size()-1){

      if(v[i].size()==0) break;

      int x=v[i][j],y=v[i][j+1];

      unite(x,y);

    }

  }



  if(!find()){

    cout<<"NO"<<endl;

  }

  else{

    cout<<"YES"<<endl;

  }



  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.4940985381087772x):


#include<bits/stdc++.h>

using namespace std;

#define inf 1000000000

#define INF 1000000000000000

#define ll long long

#define ull unsigned long long

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

#define P pair<int,int>

#define PLL pair<ll,ll>

#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)

#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)

#define rep(i,n) FOR(i,0,n)

#define rrep(i,n) RFOR(i,n,0)

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

#define IN(a,n) rep(i,n){ cin>>a[i]; }

const int vx[4] = {0,1,0,-1};

const int vy[4] = {1,0,-1,0};

#define PI 3.14159265

#define F first

#define S second

#define PB push_back

#define EB emplace_back



void init(){

  cin.tie(0);

  ios::sync_with_stdio(false);

}









struct UnionFind

{



  vector<int> par;

  vector<int> sizes;



  UnionFind(int n) : par(n), sizes(n, 1) {

    rep(i,n) par[i] = i;

  }



  int find(int x) {

    if (x == par[x]) return x;

    return par[x] = find(par[x]); 

  }



  bool unite(int x, int y) {



    x = find(x);

    y = find(y);



    if (x == y) return false;



    if (sizes[x] < sizes[y]) swap(x, y);



    par[y] = x;

    sizes[x] += sizes[y];



    return true;

  }



  int size(int x) {

    return sizes[find(x)];

  }

};



int n,m;

vector<vector<int>> v;



signed main(){

  cin>>n>>m;

  v.resize(m+1);

  rep(i,n){

    int k;

    cin>>k;

    rep(j,k){

      int l;

      cin>>l;

      v[l].EB(i);

    }

  }



  UnionFind uf(n);



  rep(i,m+1){

    FOR(j,1,v[i].size()){

      uf.unite(v[i][j-1],v[i][j]);

    }

  }



  if(uf.size(0)==n){

    cout<<"YES"<<endl;

  }

  else{

    cout<<"NO"<<endl;

  }



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

#include<algorithm>

#include<vector>

#include<queue>

#define PP std::pair<int,int>

int N, M;

std::vector<int> P[100010], L[100010];

bool usedp[100010];

bool usedl[100010];

int main() {

	std::cin >> N >> M;

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

		int K;

		std::cin >> K;

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

			int tmp;

			std::cin >> tmp;

			P[i].push_back(tmp);

			L[tmp].push_back(i);

		}

	}

	std::queue<PP> q;

	q.push({ 1,1 });

	while (!q.empty()) {

		PP p = q.front();

		q.pop();

		if (p.first == 1) {

			for (auto u : P[p.second]) {

				if (!usedl[u]) {

					usedl[u] = true;

					q.push({ 0,u });

				}

			}

		}

		else {

			for (auto u : L[p.second]) {

				if (!usedp[u]) {

					usedp[u] = true;

					q.push({ 1,u });

				}

			}

		}

	}

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

		if (!usedp[i]) {

			std::cout << "NO" << std::endl;

			return 0;

		}

	}

	std::cout << "YES" << std::endl;

	return 0;

}

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

#include<algorithm>

#include<vector>

#define PP std::pair<int,int>

int N, M;

std::vector<PP> G;

int par[200010];

int rank[200010];

void init() {

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

		par[i] = i;

		rank[i] = 0;

	}

}



int find(int x) {

	if (par[x] == x)return x;

	return par[x] = find(par[x]);

}



void unite(int x, int y) {

	x = find(x);

	y = find(y);

	if (x == y)return;

	if (rank[x] < rank[y]) {

		par[x] = y;

	}

	else {

		par[y] = x;

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

	}

}



bool same(int x, int y) {

	return find(x) == find(y);

}





int main() {

	std::cin >> N >> M;

	init();

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

		int K;

		std::cin >> K;

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

			int tmp;

			std::cin >> tmp;

			G.push_back({ i,tmp + 100000 });

		}

	}

	for (auto u : G) {

		if (!same(u.first, u.second)) {

			unite(u.first, u.second);

		}

	}

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

		if (!same(i, i + 1)) {

			std::cout << "NO" << std::endl;

			return 0;

		}

	}

	std::cout << "YES" << std::endl;

	return 0;

}