/*C: cltt的幸运数
Time Limit: 1 s Memory Limit: 128 MB
Submit
Problem Description
一棵树有n个节点，共m次查询，查询a,b的最近公共祖先是否为好数？若好数的数目是幸运数，输出YES，否则输出NO。
好数：可以表示为2的指数幂。如：1, 2，4，8，16，32，……
幸运数就是素数。
Input
nn(nn表示节点数目，接下来n−1n−1行，每行两个整数 x,yx,y 其中xx是yy的父节点）
mm(表示查询数目，接下来mm行，每行两个整数a,ba,b)
(1≤n≤105,1≤m≤10)(1≤n≤105,1≤m≤10)
Output
YESYES or NONO
Sample Input
12
1 2
1 3
2 5
3 4
3 6
4 7
7 9
7 10
6 8
8 11
8 12
4
9 8
4 7
11 12
10 7
Sample Output
YES*/
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>v[111111];
vector<int>p[111111];
bool vis[111111];
int cnt,pre[111111];
int res=0;
int ret[111111];
int find(int pos)
{
return pre[pos]=pre[pos]==pos?pos:find(pre[pos]);
}
bool check(int x)
{
if(x==1||x==0)return 0;//有可能为0
if(x==2)return 1;
for(int i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(int er,int fu)//顺序：每走一个节点找一次关系节点
{
vis[er]=1;
int num=p[er].size();
for(int i=0;i<num;i++)//此过程先进行，防止最近公共祖先为同一链上的节点影响
{
int pos=p[er][i];
if(vis[pos])
{
int ans=find(pos);
ret[res++]=ans;
//不能找一个查一个，
//因为可能有些就不存在最近公共祖先，认为是0
//因此为了这种特殊情况，为了你们比赛时避免判断的干扰。
//后台把0也当作了好数
}
}
num=v[er].size();
for(int i=0;i<num;i++)
{
int pos=v[er][i];
dfs(pos,er);
}
pre[er]=fu;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<=n;i++)
{
pre[i]=i;
}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
vis[y]=1;//有父亲
}
int o,head;
scanf("%d",&o);
cnt=0;
for(int i=0;i<o;i++)
{
int x,y;
scanf("%d%d",&x,&y);
p[x].push_back(y);
p[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
head=i;
break;
}
}
memset(vis,0,sizeof(vis));
dfs(head,-1);//cout<<res<<endl;
for(int i=0;i<o;i++){
if(!(ret[i]&(ret[i]-1)))//0&（-1）==0，
cnt++;//要全部找到后再一个一个的判断
}
/*
以后判断2的指数幂时要 x!=0&&x&(x-1)==0 才可以
*/
if(check(cnt))
printf("YES\n");
else
printf("NO\n");
return 0;
}