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

#include<vector>

#include<algorithm>



#define INF 100000000

 

using namespace std;



int gcd(int a,int b){

	if(b==0)return a;

	return gcd(b,a%b);

}

 

int V,match[1001];

bool used[1001];

vector<int>G[1001];

 

void add_edge(int u,int v){

  G[u].push_back(v);

  G[v].push_back(u);

}

 

bool dfs(int v){

  used[v]=true;

  for(int i=0;i<G[v].size();i++){

    int u=G[v][i],w=match[u];

    if(w<0 || !used[w] && dfs(w)){

      match[v]=u;

      match[u]=v;

      return true;

    }

  }

  return false;

}

 

int bipartite_matching(){

  int res=0;

  fill(match,match+1001,-1);

  for(int v=0;v<V;v++){

    if(match[v]<0){

      fill(used,used+1001,false);

      if(dfs(v))res++;

    }

  }

  return res;

}

 

int main(void){

	

	int m,n;

	

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

		vector<int>b(m),r(n);

		for(int i=0;i<1001;i++)G[i].clear();

		

		for(int i=0;i<m;i++)cin >> b[i];

		for(int i=0;i<n;i++)cin >> r[i];

		

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

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

				if(gcd(b[i],r[j])!=1)add_edge(i,j+m);

			}

		}

		V=max(m,n);

		cout << bipartite_matching() << endl;

	}

	

return 0;

}

 

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

#include <iostream>

#include<vector>



#define MAXN1 50000

#define MAXN2 50000

#define MAXM 150000



using namespace std;



int n1, n2, edges, last[MAXN1];

int preve[MAXM];

int head[MAXM];

int matching[MAXN2], dist[MAXN1], Q[MAXN1];

bool used[MAXN1], vis[MAXN1];



void init(int _n1, int _n2) {

  n1=_n1;

  n2=_n2;

  edges=0;

  fill(last, last + n1, -1);

}



void add_edge(int u, int v) {

  head[edges]=v;

  preve[edges] = last[u];

  last[u] = edges++;

}



void bfs() {

  fill(dist,dist+n1,-1);

  int sizeQ=0;

  for (int u=0;u<n1;u++) {

    if (!used[u]) {

      Q[sizeQ++]=u;

      dist[u]=0;

    }

  }

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

    int u1 = Q[i];

    for (int e=last[u1];e>=0;e=preve[e]) {

      int u2 = matching[head[e]];

      if (u2>=0 && dist[u2]<0) {

	dist[u2]=dist[u1]+1;

	Q[sizeQ++]=u2;

      }

    }

  }

}



bool dfs(int u1) {

  vis[u1]=true;

  for (int e=last[u1];e>=0;e=preve[e]) {

    int v=head[e];

    int u2=matching[v];

    if (u2<0 || (!vis[u2] && dist[u2]==dist[u1]+1 && dfs(u2))) {

      matching[v]=u1;

      return used[u1]=true;

    }

  }

  return false;

}



int bipartite_matching() {

  fill(used,used+n1,false);

  fill(matching,matching+n2,-1);

  for (int res=0;;) {

    bfs();

    fill(vis,vis+n1,false);

    int f=0;

    for(int u=0;u<n1;u++)

      if(!used[u] && dfs(u))f++;

    if (!f)return res;

    res+=f;

  }

}



int gcd(int a,int b){

    if(b==0)return a;

    return gcd(b,a%b);

}



int main(void){

  

  int m,n;

  

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

 

    init(m,n);

    

    vector<int>b(m),r(n);

    for(int i=0;i<m;i++)cin >> b[i];

    for(int i=0;i<n;i++)cin >> r[i];

    

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

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

	if(gcd(b[i],r[j])!=1)add_edge(i,j);

      }

    }



    cout << bipartite_matching() << endl;

  }

  

  return 0;

}

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

#include<vector>

#include<algorithm>

#include<cstring>

using namespace std;



#define V_MAX 1100

#define INF (1<<25)

#define pb push_back

#define sz size()

#define clr clear()



struct edge{int f,t,cost,cap,rev;};



vector<edge> G[V_MAX];

bool use[V_MAX];

int m,n;

int b[500],r[500];





void AddEdge(int from,int to,int cap){

  G[from].push_back((edge){from,to,0,cap,G[to].size()});

  G[to].push_back((edge){to,from,0,0,G[from].size()-1});

}



int dfs(int v,int t,int f){

  if(v==t)return f;

  use[v] = true;

  for(int i=0;i<(int)G[v].size();i++){

    edge &e  = G[v][i];

    if(!use[e.t] && e.cap > 0){

      int d = dfs(e.t, t,min(f,e.cap));

      if(d>0){

	e.cap -= d;

	G[e.t][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



int FordFullkerson(int s,int t){

  int flow = 0;

  for(;;){

    memset(use,0,sizeof(use));

    int tmp = dfs(s,t,INF);

    if(!tmp)return flow;

    flow += tmp;

  }

} 



int gcd(int a,int b){

  if(!b)return a;

  return gcd(b,a%b);

}



int main(){

  while(1){

    cin >> m >> n;

    if(!m && !n)break;



    for(int i=0;i<m;i++)cin >> b[i];

    for(int i=0;i<n;i++)cin >> r[i];



    for(int i=0;i<=m+n+1;i++)G[i].clr;

    for(int i=1;i<=m;i++)AddEdge(0,i,1);

    for(int i=m+1;i<=m+n;i++)AddEdge(i,m+n+1,1);



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

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

	if(gcd(b[i],r[j])>1)AddEdge(i+1,m+j+1,1);



    cout << FordFullkerson(0,m+n+1) << endl;

  }

}

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

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

#define Rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

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

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;



int gcd(int a, int b){ return b?gcd(b,a%b):a; }



int V;

vector<int> g[1010];

int match[1010];

bool use[1010];



bool dfs(int v){

  use[v] = true;

  for(int u : g[v]){

    int w = match[u];

    if(w<0 || (!use[w] && dfs(w))){

      match[u] = v;

      match[v] = u;

      return true;

    }

  }

  return false;

}



int bipartite_matching(){

  int res = 0;

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

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

    if(match[i]<0){

      memset(use,0,sizeof(use));

      if(dfs(i))res++;

    }

  }

  return res;

}



int main(){

  int m,n;

  while(cin >> m >> n){

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

    V = m+n;

    rep(i,V)g[i].clear();



    vector<int> a(m),b(n);

    rep(i,m)cin >> a[i];

    rep(i,n)cin >> b[i];



    rep(i,m)rep(j,n){

      if(gcd(a[i],b[j])!=1){

	g[i].push_back(j+m);

	g[j+m].push_back(i);

      }

    }

   

    cout << bipartite_matching() << endl;

  }

}

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

#include <vector>

using namespace std;

int n,k;int inline gcd(int a, int b) {while (b) {int c=a%b;a=b,b=c;} return a;}

vector<vector<int> >g;

vector<int>mt;

vector<char>used;

bool try_kuhn(int v) {

	if (used[v]) return false;

	used[v]=1;

	for (int i=g[v].size()-1;i>=0;i--) {

		int to=g[v][i];

		if (mt[to]==-1 || try_kuhn(mt[to])) {

			mt[to]=v;return true;

		}

	}

	return false;

}

int A[505],B[505];

int main() {

	int i,j;

	while (scanf("%d %d",&n,&k)!=EOF && (n || k)) {

		g.clear();mt.assign(k,-1);g.resize(n+k);

		for (i=0;i<n;scanf("%d",&A[i++]));

		for (i=0;i<k;scanf("%d",&B[i++]));

		for (i=0;i<n;i++) for (j=0;j<k;j++) if (gcd(A[i],B[j])>1) g[i].push_back(j);

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

			used.assign(n,false);

			try_kuhn(i);

		}

		for (i=0,j=0;i<k;i++) if (mt[i]!=-1) j++;

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

	}

	return 0;

}

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

#define N 505

int A[N],B[N],g[N][N],n,k,mt[N],used[N];

int inline gcd(int a, int b) {while (b) {int c=a%b;a=b,b=c;} return a;}

int kuhn(int v) {if (used[v]) return 0;used[v]=1;for (int i=g[v][0]-1;i;i--) {int to=g[v][i];if (mt[to]==-1 || kuhn(mt[to])) {mt[to]=v;return 1;}}return 0;}

int main() {

	int i,j;while (scanf("%d %d",&n,&k)!=EOF && (n || k)) {

		for (i=0;i<k;mt[i++]=-1);

		for (i=0;i<n;g[i][0]=1,scanf("%d",&A[i++]));for (i=0;i<k;scanf("%d",&B[i++]));

		for (i=0;i<n;i++) for (j=0;j<k;j++) if (gcd(A[i],B[j])>1) g[i][g[i][0]++]=j;

		for (i=0;i<n;i++) {for (j=0;j<n;used[j++]=0);kuhn(i);}

		for (i=0,j=0;i<k;j+=(mt[i]!=-1),i++);printf("%d\n",j);

	}

	return 0;

}

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

#define pb       push_back

#define mp       make_pair

#define mod      1000000007

#define first    ff

#define second   ss

#define pi       acos(-1.0)

#define test     int t;cin>>t;while(t--)

typedef long long ll;

using namespace std;

vector<int>node[10001];

ll bigmod(ll a,ll b)

{

    ll  res=1;

    a=a%mod;

    if(a==0)

        return 0;

    while(b>0)

    {



           if(b%2)

            res=(res*a)%mod;

            b=b>>1;

            a=(a*a)%mod;

    }

    return res;

}

int main()

{      





     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     

     int n;

     cin>>n;



     ll ans=(bigmod(10,n)-(2*bigmod(9,n))%mod+bigmod(8,n))%mod;

     if(ans<0)

        cout<<ans+mod<<endl;

     else

     cout<<ans<<endl;



      return 0;

    

 }   

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

using namespace std;

#define ll long long

ll mod(ll n,ll m)

{

    ll ans=1;

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

    {

        ans=(ans*m)%1000000007;

    }

    return ans;

}

int main()

{

    ll n;cin>>n;

    ll ans=(((mod(n,10)-2*mod(n,9)+mod(n,8))%1000000007)+1000000007)%1000000007;

    cout<<ans<<endl;

    return 0;

}


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

#include <cstring> 

#include <cmath>

#include <cstdio>

const long long mod=1e9+7;

using namespace std;

long long f(long long m,long long n){

	long long ans=1;

	while(n>0){

		if(n&1)

			ans=(ans*m)%mod;

		m=(m*m)%mod;

		n=(n/2)%mod;

	}

	return ans;

}

int main(){

	long long n;

	scanf("%lld",&n);	

		cout<<(f(10,n)%mod-(2*f(9,n))%mod+f(8,n)%mod+mod)%mod<<endl;	

	return 0;

}

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

#include<string>

#include<math.h>



using namespace std;



typedef long long ll;

const ll mod = 1e9 + 7;

ll N;



ll find(ll a,ll b){

	ll sum=1;

	while(b){

		if(b&1) sum=(sum*a)%mod;

		a=(a*a)%mod;

		b=b/2;

	}

	return sum;

}



int main(){

	scanf("%lld",&N);



	ll ans=find(10,N)-find(9,N)-find(9,N)+find(8,N);

	printf("%lld",(ans%mod+mod)%mod);



	return 0;

}

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

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF=1001001001;

const int mod=1e9+7;

int64_t dp[1000005][2][2];

int main() {

  int N;

  cin>>N;

  dp[0][0][0]=8,dp[0][1][0]=1,dp[0][0][1]=1;

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

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

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

        if(dp[i][j][k]==0){continue;}

        for(int next=0;next<=9;next++){

          if(next==0){

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

          }

          else if(next==9){

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

          }

          else{

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

          }

        }

      }

    }

  }

  //cout<<dp[1][0][1]<<endl;

  cout<<dp[N-1][1][1]<<endl;

  return 0;

}

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

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF=1001001001;

const int mod=1e9+7;



int64_t N;

int64_t powmod(int64_t x){

  int64_t res=1;

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

    (res*=x)%=mod;

  }

  return res;

}

int main() {

  cin>>N;

  int64_t ans=powmod(10)-powmod(9)-powmod(9)+powmod(8);

  ans%=mod;

  ans=(ans+mod)%mod;

  cout<<ans<<endl;

  return 0;

}

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

#include <algorithm>

#include <utility>

#include <vector>

#include <string>



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

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

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)

#define RFOR(i, a, b) for (int i = (a); i > (b); i--)

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

const ll MOD = 1e9 + 7;

ll dp[1000001][2][2];



int main() {

    int N;

    cin >> N;

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

    REP(i, N) REP(j, 2) REP(k, 2) REP(d, 10) {

        dp[i + 1][j || d == 0][k || d == 9] += dp[i][j][k];

        dp[i + 1][j || d == 0][k || d == 9] %= MOD;

    }

    cout << dp[N][1][1] << endl;

    return 0;

}

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

#include <algorithm>

#include <utility>

#include <vector>

#include <string>



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

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

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)

#define RFOR(i, a, b) for (int i = (a); i > (b); i--)

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

const ll MOD = 1e9 + 7;



ll power(int x, int y) {

    if (y == 0) return 0;

    if (y == 1) return x;

    ll p = power(x, y >> 1);

    if (y & 1) return p * p % MOD * x % MOD;

    else return p * p % MOD;

}



int main() {

    int N;

    cin >> N;

    ll ans = power(10, N) - 2 * power(9, N) + power(8, N);

    cout << (ans + 2 * MOD) % MOD << endl;

    return 0;

}

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

#define lli long long

using namespace std;

lli mod=1e9+7;





lli black[100000+5];

lli white[100000+5];

vector<int>edge[100010];



void dpp(int v,int par)

{

   bool fl=0;

   white[v]=black[v]=1;

   for(int x:edge[v])

   {

     if(x==par)

     continue;

     fl=1;



     dpp(x,v);

     black[v]*=(white[x]);

     if(black[v]>=mod)

     black[v]%=mod;

     white[v]*=(white[x]+black[x]);

     if(white[v]>=mod)

     white[v]%=mod;



   }







}



int main()

{

   int n;

   cin>>n;



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

   {

     int a,b;

     cin>>a>>b;

     edge[a].push_back(b);

     edge[b].push_back(a);

   }

   dpp(1,-1);



   cout <<(white[1]+black[1])%mod;

}










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

#include <vector>

#include <limits.h>

#include <algorithm>

#include <string>

#include <math.h>

#include <limits.h>

#include <queue>

#include <map>

#include <set>

#include <iomanip>

#include <bitset>

#include <cassert>

#include <random>

#include <functional>

#include <stack>

#include <iomanip>

using namespace std;

int MOD = 1e9 + 7;



int N;

typedef pair<int, int> pii;   //自分、親

vector<vector<int>> G;   //グラフ

vector<pii> order;



void setorder() {

	vector<bool> check;

	check.resize(N, false);   //来た->true

	queue<pii> st;

	st.push(pii(0,-1));

	while (!st.empty()) {

		pii cur = st.front();

		st.pop();

		check[cur.first] = true;

		order.push_back(cur);

		for (int next : G[cur.first]) {

			if (check[next])continue;

			st.push(pii(next, cur.first));

		}

	}

}



int main() {

	cin >> N;

	G.resize(N);

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

		int u, v;

		cin >> u >> v;

		G[--u].push_back(--v);

		G[v].push_back(u);

	}

	setorder();

	vector<long long> DP[2];

	DP[0].resize(N, 1);

	DP[1].resize(N, 1);

	for (int ord = N - 1; ord >= 0; ord--) {

		pii cur = order[ord];

		//葉っぱの場合

		if (G[cur.first].size() == 1 && G[cur.first][0] == cur.second) {

			DP[0][cur.first] = 1;

			DP[1][cur.first] = 1;

		}

		if (cur.second == -1)continue;

		DP[0][cur.second] *= (DP[0][cur.first]+DP[1][cur.first]);

		DP[1][cur.second] *= (DP[0][cur.first]);

		DP[0][cur.second] %= MOD;

		DP[1][cur.second] %= MOD;

	}

	cout << (DP[0][0] + DP[1][0]) % MOD << endl;

	return 0;

}

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

using namespace std;

#define N 100500

#define pb push_back

#define mp make_pair

#define fi first

#define se second

typedef long long ll;

const ll m = 1e9 + 7;

int n;

ll memo[N][5];

vector <int> adj[N];



ll mul(ll a , ll b) {

    return ((a % m) * (b % m)) % m;

}



ll add(ll a , ll b) {

    return ((a % m) + (b % m)) % m;

}



ll dp(int u , int color , int par) {

    ll &sol = memo[u][color];

    if (sol != -1) return sol;

    ll product = 1;

    for (int v : adj[u]) {

        if (v == par) continue;

        if (color == 0) {

            product = mul(product , add(dp(v , 0 , u) , dp(v , 1 , u)));

        } else {

            product = mul(product , dp(v , 0 , u));

        }

    }

    return sol = product;

}



int main() {

    scanf("%d" , &n);

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

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

        adj[u].pb(v);

        adj[v].pb(u);

    }

    memset (memo , -1 , sizeof memo);

    printf("%lld\n" , add(dp(1 , 0 , 1) , dp(1 , 1 , 1)));

}


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

#include <vector>

#include <limits.h>

#include <algorithm>

#include <string>

#include <math.h>

#include <limits.h>

#include <queue>

#include <map>

#include <set>

#include <iomanip>

#include <bitset>

#include <cassert>

#include <random>

#include <functional>

#include <stack>

#include <iomanip>

using namespace std;

int MOD = 1e9 + 7;



int N;

typedef pair<int, int> pii;   //自分、親

vector<vector<int>> G;   //グラフ

vector<pii> order;



void setorder() {

	vector<bool> check;

	check.resize(N, false);   //来た->true

	queue<pii> st;

	st.push(pii(0,-1));

	while (!st.empty()) {

		pii cur = st.front();

		st.pop();

		check[cur.first] = true;

		order.push_back(cur);

		for (int next : G[cur.first]) {

			if (check[next])continue;

			st.push(pii(next, cur.first));

		}

	}

}



int main() {

	cin >> N;

	G.resize(N);

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

		int u, v;

		cin >> u >> v;

		G[--u].push_back(--v);

		G[v].push_back(u);

	}

	setorder();

	vector<long long> DP[2];

	DP[0].resize(N, 1);

	DP[1].resize(N, 1);

	for (int ord = N - 1; ord >= 0; ord--) {

		pii cur = order[ord];

		//葉っぱの場合

		if (G[cur.first].size() == 1 && G[cur.first][0] == cur.second) {

			DP[0][cur.first] = 1;

			DP[1][cur.first] = 1;

		}

		if (cur.second == -1)continue;

		DP[0][cur.second] *= (DP[0][cur.first]+DP[1][cur.first]);

		DP[1][cur.second] *= (DP[0][cur.first]);

		DP[0][cur.second] %= MOD;

		DP[1][cur.second] %= MOD;

	}

	cout << (DP[0][0] + DP[1][0]) % MOD << endl;

	return 0;

}

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

#include <queue>

#define mod 1000000007



using namespace std;

int n,i,x,y;

struct nodS

{

    int parent=0;

    bool viz=false;

    long long dpa=1, dpb=1;

    vector <int> vecini;

} nod[100005];

struct poz

{

    int parent, id;

    poz(int id, int parent)

    {

        this->id=id;

        this->parent=parent;

    }

};

queue <poz> q;

void rezfunc(int poz)

{

    for(auto it : nod[poz].vecini)

    {

        if(it!=nod[poz].parent)

        {

            rezfunc(it);

            nod[poz].dpa*=(nod[it].dpa+nod[it].dpb);

            nod[poz].dpa%=mod;

            nod[poz].dpb*=nod[it].dpa;

            nod[poz].dpb%=mod;

        }

    }

}

int main()

{

    cin>>n;

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

    {

        cin>>x>>y;

        nod[x].vecini.push_back(y);

        nod[y].vecini.push_back(x);

    }

    for(auto it : nod[1].vecini)

    {

        q.push(poz(it, 1));

    }





    while(!q.empty())

    {

        poz curr=q.front();

        nod[curr.id].parent=curr.parent;

        for(auto it : nod[curr.id].vecini)

            if(it!=curr.parent)

            {

                q.push(poz(it, curr.id));

            }



        q.pop();

    }



    /*

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

    {

        cout<<nod[i].parent<<' ';

    }

    */



    rezfunc(1);

    /*

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

    {

        cout<<nod[i].dpa<<' '<<nod[i].dpb<<'\n';

    }

    */



    cout<<(nod[1].dpa+nod[1].dpb)%mod;

    return 0;

}

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

#include <ext/pb_ds/assoc_container.hpp>

#define fastio() ios_base::sync_with_stdio(false);

#define rmod(x, y) ((((x)%(y))+(y))%(y))

using namespace std;

using namespace __gnu_pbds;

typedef long long ll;

typedef long double ld;

template<typename T, typename R = null_type, typename C = less<T>>

tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update> ordered_set(){

	return tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update>();

}





const int maxn = 1e5+5, mod = 1e9+7;



int add(int a, int b){return (a+b)%mod;}

int mul(ll a, ll b){return (a*b)%ll(mod);}

int n, x, y, dp[maxn][2];

vector<int> vs[maxn];



int dfs(int v, int p, bool col){

	if (dp[v][col] != -1) return dp[v][col];

	int ret = dp[v][col];

	ret = 1;

	for(int e: vs[v]) if (e != p){

		int t = dfs(e, v, 1);

		if (col) t = add(t, dfs(e, v, 0));

		ret = mul(ret, t);

	}

	return dp[v][col] = ret;

}



int main(){

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

	scanf("%d", &n);

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

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

		vs[--x].push_back(--y);

		vs[y].push_back(x);

	}

	dfs(0, -1, 1);

	dfs(0, -1, 0);

	printf("%d\n", add(dp[0][0], dp[0][1]));

	return 0;

}


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

#include <vector>

using namespace std;

using ll = long long;

#define in(v) v; cin >> v;

void ins() {}

template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

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



template<int MOD> struct MInt {

  long long val;

  MInt(long long val = 0) : val(val % MOD) { if (val < 0) val += MOD; }

  MInt operator+(const MInt& n) const { return MInt(val) += n; }

  MInt operator*(const MInt& n) const { return MInt(val) *= n; }

  MInt operator/(const MInt& n) const { return MInt(val) /= n; }

  MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; }

  MInt& operator*=(const MInt& n) { val = (val * n.val) % MOD; return *this; }

  friend ostream& operator<<(ostream& os, const MInt& n) { os<<n.val; return os; }

};

using mint = MInt<1000000007>;



struct Graph {

  vector<vector<int>> edge;

  Graph(int n = 0) { resize(n); }

  void resize(int n) {

    edge.resize(n, vector<int>());

  }

  void addEdge(int from, int to, bool directed = false) {

    edge[from].push_back(to);

    if (!directed)

      edge[to].push_back(from);

  }

};

Graph G;



constexpr int MAX_N = 1e5+1;

bool visited[MAX_N][2];

mint dp[MAX_N][2];

mint dfs(int cur, int parent, bool filled) {

  if (visited[cur][filled])

    return dp[cur][filled];

  mint ans = 1;

  for (const auto& to : G.edge[cur]) {

    if (to == parent)

      continue;

    ans *= filled ? dfs(to, cur, false)

      : dfs(to, cur, true) + dfs(to, cur, false);

  }

  visited[cur][filled] = true;

  return dp[cur][filled] = ans;

}



int main() {

  int in(N);

  G.resize(N);



  rep(i, N-1) {

    int x, y;

    ins(x, y);

    --x, --y;

    G.addEdge(x, y);

  }



  cout << dfs(0, -1, false) + dfs(0, -1, true) << endl;



  return 0;

}


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

#include <vector>

using namespace std;

#define in(v) v; cin >> v;

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



struct Graph {

  vector<vector<int>> edge;

  Graph(int n = 0) { resize(n); }

  void resize(int n) { edge.resize(n, vector<int>()); }

  void addEdge(int from, int to) {

    edge[from].push_back(to); edge[to].push_back(from);

  }

  const vector<int>& operator[](int from) const { return edge[from]; }

};

constexpr int MOD = 1e9+7, MAX_N = 1e5;

long long dp[MAX_N][2];

long long dfs(const Graph &G, int cur, int prev, bool filled) {

  if (dp[cur][filled] != -1) return dp[cur][filled];

  long long ans = 1;

  for (const auto& to:G[cur]) {

    if (to == prev) continue;

    ans *= filled

      ? dfs(G, to, cur, false)

      : (dfs(G, to, cur, false) + dfs(G, to, cur, true)) % MOD;

    ans %= MOD;

  }

  return dp[cur][filled] = ans;

}

int main() {

  int in(N);



  Graph G(N);

  rep(i, N)

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

  rep(i, N-1) {

    int in(x); int in(y);

    --x, --y;

    G.addEdge(x, y);

  }



  cout << (dfs(G, 0, -1, true) + dfs(G, 0, -1, false)) % MOD << endl;



  return 0;

}


// Fastest known solution for this problem: