stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//problem:T99402

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define mk make_pair

#define lob lower_bound

#define upb upper_bound

#define fst first

#define scd second



typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;



inline int read(){

	int f=1,x=0;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

inline ll readll(){

	ll f=1,x=0;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}



const int MAXN=1e5+5;

ll dis[MAXN];

struct EDGE{int nxt,to,w;}edge[MAXN*10+100];

int n,head[MAXN],tot;

inline void add_edge(int u,int v,int w){edge[++tot].nxt=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;}

struct RULE{bool operator()(int &x,int &y)const{return dis[x]>dis[y];}};

int main() {

	n=read();if(n==1){puts("1");return 0;}

	for(int i=0;i<n;++i)for(int j=0;j<10;++j)add_edge(i,(i*10+j)%n,j);

	for(int i=1;i<10;++i)add_edge(n,i,i);

	memset(dis,0x3f,sizeof(dis));dis[n]=0;priority_queue<int,vector<int>,RULE>q;q.push(n);

	while(!q.empty()){

		int u=q.top();q.pop();

		//if(u==0){cout<<dis[u]<<endl;return 0;}

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

			int v=edge[i].to;

			if(dis[v]>dis[u]+edge[i].w){

				dis[v]=dis[u]+edge[i].w;

				q.push(v);

			}

		}

	}cout<<dis[0]<<endl;return 0;

}

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

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define mk make_pair

#define lob lower_bound

#define upb upper_bound

#define fst first

#define scd second



typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;



inline int read(){

	int f=1,x=0;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

inline ll readll(){

	ll f=1,x=0;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}



const int MAXN=1e6+5;

int n;

bool vis[MAXN];

int main() {

	n=read();if(n==1){puts("1");return 0;}

	deque<pii>dq;dq.pb(mk(1,1));

	while(!dq.empty()){

		pii u=dq.front();dq.pop_front();

		if(vis[u.fst])continue;

		if(u.fst==0){cout<<u.scd<<endl;return 0;}

		vis[u.fst]=1;

		dq.push_front(mk(u.fst*10%n,u.scd));

		dq.push_back(mk((u.fst+1)%n,u.scd+1));

	}return 0;

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

#include <algorithm>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#define MOD 1000000007

typedef long long ll;

using namespace std;



#define INFTY (1<<30)

#define MAX 100010



int n;

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



void dijkstra(){

  priority_queue<pair<int,int>> PQ;

  int d[MAX];

  for(int i=0;i<n;i++) d[i]=INFTY;



  d[1]=0;

  PQ.push(make_pair(0,1));



  while(!PQ.empty()){

    pair<int,int> f=PQ.top();

    //cout<<f.first<<" "<<f.second<<endl;

    PQ.pop();

    int u=f.second;



    if(d[u]<f.first*(-1)) continue;



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

      int v=adj[u][j].first;

      if(d[v]>d[u]+adj[u][j].second){

        d[v]=d[u]+adj[u][j].second;

        PQ.push(make_pair(d[v]*(-1),v));

      }

    }

  }



  cout<<d[0]+1<<endl;

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

    cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;

  }*/

}



int main(){

  cin>>n;

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

    adj[i].push_back(make_pair((i+1)%n,1));

    adj[i].push_back(make_pair((i*10)%n,0));

    //cout<<i<<" "<<(i+1)%n<<" "<<i*10%n<<endl;

  }

  dijkstra();

  return 0;

}


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

#include <algorithm>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#include <deque>

#define MOD 1000000007

typedef long long ll;

using namespace std;



#define INFTY (1<<30)

#define MAX 100010



int main(){

  int k;

  cin>>k;



  deque<pair<int,int>> DQ;

  int d[k+1]={};

  for(int i=0;i<k;i++) d[i]=INFTY;

  DQ.push_back(make_pair(1,0));



  while(!DQ.empty()){

    pair<int,int> p=DQ.front();

    DQ.pop_front();

    int f=p.first;

    if(d[f]!=INFTY) continue;

    d[f]=p.second;



    DQ.push_front(make_pair((f*10)%k,d[f]));

    DQ.push_back(make_pair((f+1)%k,d[f]+1));

  }



  cout<<d[0]+1<<endl;



  return 0;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x; i <= n; i++)

#define rep3(i, x, n) for(int i = x; i >= n; i--)

#define elif else if

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

#define pb(x) push_back(x)

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

using ll = long long;

using ld = long double;

using pii = pair<int, int>;

using pil = pair<int, ll>;

using pli = pair<ll, int>;

using pll = pair<ll, ll>;

const ll MOD = 1e9+7;

//const ll MOD = 998244353;

const int inf = 1e9;

const ll INF = 1e18;

const ld EPS = 1e-10;



struct edge{int to, cost;};



const int MAX_V = 1e5;

vector<edge> es[MAX_V];

vector<int> d(MAX_V, inf);



void add_edge(int from, int to, int cost){

    es[from].emplace_back((edge){to, cost});

}



void dijkstra(int s){

    d[s] = 0;

    queue<pii> que;

    que.push(pii(d[s], s));

    while(!que.empty()){

        pii p = que.front();

        que.pop();

        int i = p.second;

        if(p.first > d[i]) continue;

        for(auto &e: es[i]){

            if(d[e.to] > d[i]+e.cost){

                d[e.to] = d[i]+e.cost;

                que.push(pii(d[e.to], e.to));

            }

        }

    }

}



int main(){

    int K;

    cin >> K;

    rep(i, K){

        add_edge(i, (i+1)%K, 1);

        add_edge(i, (i*10)%K, 0);

    }

    dijkstra(1);

    cout << d[0]+1 << endl;

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x; i <= n; i++)

#define rep3(i, x, n) for(int i = x; i >= n; i--)

#define elif else if

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

#define pb push_back

#define eb emplace_back

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

#define sz(x) (int)x.size()

using ll = long long;

using ld = long double;

using pii = pair<int, int>;

using pil = pair<int, ll>;

using pli = pair<ll, int>;

using pll = pair<ll, ll>;

const ll MOD = 1e9+7;

//const ll MOD = 998244353;

const int inf = (1<<30)-1;

const ll INF = (1LL<<60)-1;

const ld EPS = 1e-10;

template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};

template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};



int main(){

    int K;

    cin >> K;

    vector<int> es[K][2];

    rep(i, K){

        es[i][0].pb((i*10)%K);

        es[i][1].pb((i+1)%K);

    }

    int d[K];

    fill(d, d+K, inf);

    d[1] = 1;

    deque<int> que;

    que.push_back(1);

    while(!que.empty()){

        int i = que.front(); que.pop_front();

        for(auto &e: es[i][0]){

            if(chmin(d[e], d[i])) que.push_front(e);

        }

        for(auto &e: es[i][1]){

            if(chmin(d[e], d[i]+1)) que.push_back(e);

        }

    }

    cout << d[0] << endl;

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

#define ll long long

using namespace std;

const int N = 400001;





int sum(ll n){

  int res = 0;

  while(n){

    res += n % 10;

    n /= 10;

  }

  return res;

}

bitset<100001> bb[2];

int main()

{

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

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

  int k;

  cin >> k;

  set<int> ss;

  int x = 1;

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

    x *= 10;

    x %= k;

    ss.insert(x);

  }

  if(*ss.begin() == 0){

    cout << 1;

    return 0;

  }

  for(auto el : ss){

    bb[1][el] = 1;

  }

  int lim = sum(k);

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

    bb[i&1] = bb[i&1^1];

    for(auto el : ss){

      bb[i&1] |= (bb[i&1^1] << el);

      bb[i&1] |= (bb[i&1^1] >> (k - el));

      if(bb[i&1][0]){

//        cout << el << endl;

        cout << i;

        return 0;

      }

    }

  }

  cout << lim;

}


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

#define ll long long

using namespace std;

const int N = 100001;



int bfs(int k){

  deque<int> x;

  x.push_back(1);

  int dist[100001];

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

    dist[i] = 10000;

  dist[1] = 1;

  while(x.size()){

    int u = x.front();x.pop_front();

    if(u == 0)

      return dist[u];

    if(dist[u] < dist[10 * u % k]){

      x.push_front(10 * u % k);

      dist[10 * u % k] = dist[u];

    }

    if(dist[u] + 1 < dist[(u + 1) % k]){

      dist[(u + 1) % k] = dist[u] + 1;

      x.push_back((u + 1) % k);

    }

  }

}

int main()

{

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

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

  int k;

  cin >> k;

  cout << bfs(k);

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

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100010;



char str[maxn], cur[maxn];

int len;

int l[maxn];



void init()

{

	memset(l,0,sizeof(l));

	int cnt = 0;

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

	{

		if (str[i] == '0' || i == len)

		{

			for (int j=i-cnt;j<=i-1;j++) l[j] = cnt;

			cnt = 0;

			continue;

		}

		cnt++;

	}

	//for (int i=0;i<len;i++) cout<<l[i]<<" ";

	//cout<<endl;

}



bool check(int k)

{

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

	{

		if (str[i] == '0') continue;

		if (i >= k || len-1-i>=k) continue;

		if (l[i] >= k) continue;

		return false;

	}

	return true;

}



int main()

{

	//freopen("D.in","r",stdin);

	scanf("%s",str);





	len = strlen(str);

	init();

	int lb = 1, ub = len + 1;

	while (ub > lb + 1)

	{

		int mid = (lb + ub)/2;

		if (check(mid)) lb = mid;

		else ub = mid;

	}



	for (int i=0;i<len;i++) str[i] = (str[i]=='1')?'0':'1';

	init();

	int lb2 = 1, ub2 = len + 1;

	while (ub2 > lb2 + 1)

	{

		int mid = (lb2 + ub2)/2;

		if (check(mid)) lb2 = mid;

		else ub2 = mid;

	}



	printf("%d\n",max(lb,lb2));

	return 0;

}


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

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100010;



char str[maxn];



int main()

{

	//freopen("D.in","r",stdin);

	scanf("%s",str);

	int len = strlen(str);



	int ans = len;

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

	{

		if (str[i] != str[i+1]) ans = min(ans, max(i+1,len-1-(i+1)+1));

	}



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

	return 0;

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

using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



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

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

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll)1e15;



ll N;

string S;

ll T[100005];

bool check(ll k)

{

    REP(n, 2)

    {

        memset(T, 0, sizeof(T));

        ll m = 0;

        string s = "";

        REP(i, N)

        {

            m += T[i];

            ll t = (S[i] - '0' + m) % 2;



            if (i + k <= N && t != n)

            {

                m++;

                T[i + k] = -1;

                t = (t + 1) % 2;

            }

            s.push_back(t + '0');

        }



        ll max = 0;

        ll sum = 0;

        REP(i, N)

        {

            sum++;

            if (i == N - 1 || s[i] != s[i + 1])

            {

                max = std::max(max, sum);

                sum = 0;

            }

        }



        if (max >= k)

            return true;

    }

    return false;

}



int main()

{

    cin >> S;

    N = S.length();

    ll ok = 1, ng = N + 1;

    while (abs(ok - ng) > 1)

    {

        ll mid = (ok + ng) / 2;

        if (check(mid))

            ok = mid;

        else

            ng = mid;

    }

    cout << ok << endl;



    return 0;

}

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



using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



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

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

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll) 1e15;



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    string S;

    cin >> S;

    ll N = S.length();

    bool e = true;

    REP(i, N - 1) {

        if (S[i] != S[i + 1])

            e = false;

    }

    ll ans = INF;

    REP(i, N - 1) {

        if (S[i] == S[i + 1])

            continue;

        ans = std::min(ans, std::max(i + 1, N - 1 - i));

    }

    if (e)

        ans = N;

    cout << ans << endl;

    return 0;

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

#include<algorithm>

#define maxn 100005

#define inf 0x3f3f3f3f

using namespace std;

typedef long int ll;

int main()

{

    string s;

    cin >> s;

    int ls = s.size(), ans = ls;

    for (int i = 1; i < ls; ++i) if (s[i - 1] != s[i]) ans = min(ans, max(i, ls - i));

    cout << ans << endl;

    return 0;

}


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

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int inf=1<<29;

const int maxn=1e5+100;

char s[maxn];



int main()

{

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

    while (scanf("%s",s+1)!=EOF)

    {

        int len=strlen(s+1);

        int ans=inf;

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

        {

            if (s[i]!=s[i+1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

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

using namespace std;



const int maxn = 1e5+100;

char s[maxn];



int main()

{

    while (scanf("%s",s)!=EOF)

    {

        int l = strlen(s);

        int k = 0, ans = l;

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

            if (abs(s[i-1] - s[i]) == 1)

            {

                k = max(i,l-i);

                ans = min(ans,k);

            }

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

    }

    return 0;

}


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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

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

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<iostream>

#include<algorithm>

#include<map>

#include<set>

#include<stack>

#include<time.h>

#include<queue>

#include<bitset>

#include<vector>

using namespace std;

const int maxn=1e5+100;

char a[maxn];

int main()

{

    scanf("%s",a);

    int len=strlen(a),ans=len;

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

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

            ans=min(ans,max(i,len-i));

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

    return 0;

}

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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

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

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <cstdlib>

#include <vector>

#include <map>

#include <cstring>

using namespace std;

const int maxn=2e6+100;

const long long mod=1e12+7;

long long ans,l1,l2,len1,len2,ty,z,n,m,k,t,x,y;

set<long long>s;char c[maxn];bool le;char tt;

long long h[maxn];

int main()

{

  //  freopen("x.in","r",stdin);

  //  freopen("x.out","w",stdout);

  scanf("%s",c);

  k=strlen(c);

  ans=k;

  for(long long i=1;i<k;++i)

  {

      if(c[i]!=c[i-1])

      ans=min(ans,max(i,k-i));

  }

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

  //  fclose(stdin);

   // fclose(stdout);

    return 0;

}


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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

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

using namespace std;

typedef pair<int,int> par;

int read(){

	int x=0,f=1; char ch=getchar();

	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}

	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}

	return x*f;

}

int fa[1000005];

map <par,int>m,a;

multiset<int>s[100005];

queue<par>q;

par makep(int x,int y){

	if (x>y) return par(y,x);

	else return par(x,y);

}

int find(int x){

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

}

int main(){

	int n=read();

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

		int u=read(),v=read();

		par w=makep(u,v);

		m[w]++; 

		if (m[w]>1&&a[w]==0){

			a[w]=1; q.push(w);

		}

		if (i<=n) fa[i]=i; 

		s[v].insert(u); s[u].insert(v);

	}

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

		int x,y;

		while (1){

			if (q.empty()){printf("NO\n"); return 0;}

			par w=q.front(); q.pop();

			x=find(w.first); y=find(w.second);

			if (x!=y) break;

		}

		if (s[x].size()>s[y].size()) swap(x,y);

		fa[x]=y;

		for (set<int>::iterator i=s[x].begin();i!=s[x].end();i++){

			int v=find(*i);

			if (v==y) continue;

			par z=makep(v,y);

			m[z]++; 

			if (m[z]>1&&a[z]==0){

				q.push(z); a[z]=1;

			}

			s[v].erase(s[v].find(x)); s[y].insert(v); s[v].insert(y);

		}

		s[y].erase(x);

		s[x].clear();

	}

	printf("YES\n");

	return 0;

}

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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

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

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

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

#include<cstring>

#include<cstdlib>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=100005;



int N;

set<int> E[MAXN];

map<int,int> cnt[MAXN];

queue<pair<int,int>> Q;



int fa[MAXN];

int Root(int x)

{return fa[x]==0?x:(fa[x]=Root(fa[x]));}



void Link(int u,int v)

{

    E[u].insert(v);

    E[v].insert(u);

    if(u>v)

        swap(u,v);

    cnt[u][v]++;

    if(cnt[u][v]>2)

    {

        puts("NO");

        exit(0);

    }

    if(cnt[u][v]==2)

        Q.emplace(u,v);

}

void Cut(int u,int v)

{

    E[u].erase(v);

    if(u>v)

        swap(u,v);

    cnt[u].erase(v);

}



int main()

{

    scanf("%d",&N);

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

    {

        int u,v;

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

        Link(u,v);

    }

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

    {

        int u,v;

        do

        {

            if(Q.empty())

            {

                puts("NO");

                return 0;

            }

            u=Root(Q.front().first),v=Root(Q.front().second);

            Q.pop();

        }while(u==v);

        if(E[u].size()<E[v].size())

            swap(u,v);

        fa[v]=u;

        Cut(u,v);

        for(auto e:E[v])

        {

            int t=Root(e);

            if(t==u)

                continue;

            Link(t,u);

            Cut(t,v);

        }

    }

    puts("YES");



    return 0;

}


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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

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

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

}