#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define mpa make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define bc back()
#define ar array
#define vll vector<ll>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;*/
template <class _T>
bool chmin(_T &x, const _T &y){
if(x>y){
x=y;
return true;
}
return false;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag=false;
if (x<y){
x=y;flag|=true;
}
return flag;
}
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=2e5+7;
const ld eps=1e-9;
vector<vll> g(N);
vector<pair<ll,ll>> pr(N);
ll d[N],p[N][20];
ll tin[N],tout[N],t;
void dfs(ll v){
tin[v]=++t;
for(ll i=1;i<19;i++) p[v][i]=p[p[v][i-1]][i-1];
for(auto i : g[v]){
if(p[v][0]==i)continue;
p[i][0]=v;
d[i]=d[v]+1;
dfs(i);
}
tout[v]=++t;
}
ll lca(ll a,ll b){
if(d[b]>d[a])swap(a,b);
ll i;
for(i=18;i>=0;i--){
if(d[a]-d[b]>=(1ll<<i)){
a=p[a][i];
}
}
if(a==b)return b;
for(i=18;i>=0;i--){
if(p[a][i]!=p[b][i]){
a=p[a][i];
b=p[b][i];
}
}
return p[a][0];
}
bool par(ll p,ll ch){
return (tin[p]<=tin[ch] && tout[ch]<=tout[p]);
}
bool on_path(ll a,ll x,ll y){
ll lc=lca(x,y);
if(!par(lc,a))return false;
if(par(a,x) || par(a,y))return true;
return false;
}
void solve(){
ll i,j;
ll n,m;
ll a,b;
cin>>n;
for(i=1;i<=n;i++){
g[i].clear();
for(j=0;j<20;j++)p[i][j]=0;
d[i]=tin[i]=t=tout[i]=0;
}
bool bamboo=true;
for(i=1;i<n;i++){
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
if(a+1!=b)bamboo=false;
}
if(bamboo){
cin>>m;
ll l=0;
vector<pair<ll,ll>> v;
for(i=0;i<m;i++){
cin>>a>>b;
v.pb({a,b});
}
sort(all(v));
for(i=0;i<m;i++){
a=v[i].fr,b=v[i].sc;
if(b<=l){
cout<<"No"<<endl;
return;
}
l=max(l,b);
}
cout<<"Yes"<<endl;
return;
}
dfs(1);
cin>>m;
map<ll,ll> mp,mp2;
for(i=0;i<m;i++) {
cin>>pr[i].fr>>pr[i].sc;
if(mp[pr[i].fr]){
cout<<"No"<<endl;
return;
}mp[pr[i].fr]++;
if(mp2[pr[i].sc]){
cout<<"No"<<endl;
return;
}mp2[pr[i].sc]++;
}
a=pr[0].fr,b=pr[0].sc;
ll x=pr[1].fr,y=pr[1].sc;
if(par(b,y) && !par(a,y)){cout<<"No"<<endl;return;}
else if(par(a,y) && !par(b,y)){cout<<"No"<<endl;return;}
if(on_path(y,a,b) && on_path(b,x,y)){cout<<"No"<<endl;return;}
if(on_path(a,x,y) && on_path(b,x,y)){cout<<"No"<<endl;return;}
swap(a,x);
swap(b,y);
if(par(b,y) && !par(a,y)){cout<<"No"<<endl;return;}
else if(par(a,y) && !par(b,y)){cout<<"No"<<endl;return;}
if(on_path(y,a,b) && on_path(b,x,y)){cout<<"No"<<endl;return;}
if(on_path(a,x,y) && on_path(b,x,y)){cout<<"No"<<endl;return;}
cout<<"Yes"<<endl;
/*bool dp[(1ll<<(m+5))];
memset(dp,false,sizeof(dp));
dp[0]=true;
vector<vll> v(m+5);
for(ll mask=0;mask<(1ll<<m);mask++){
ll c=0;
for(i=0;i<m;i++){
if(mask&(1ll<<i))c++;
}
v[c].pb(mask);
}
for(i=1;i<=m;i++){
for(auto j : v[i]){
vector<ll> cur;
for(ll bit=0;bit<m;bit++){
if(j&(1ll<<bit)){
cur.pb(bit);
}
}
for(auto x : cur){
if(!dp[j^(1ll<<x)])continue;
bool flag=true;
for(auto y : cur){
if(x==y)continue;
if(!can_pass(x,y) && !can_pass(y,x)){flag=false;break;}
}
if(flag){dp[j]=true;break;}
}
}
}
if(dp[(1ll<<m)-1])cout<<"Yes"<<endl;
else cout<<"No"<<endl;*/
}
signed main(){
//start();
ll t=1;
cin>>t;
while(t--) solve();
return 0;
}
/*
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/
Compilation message
travel.cpp: In function 'void fre(std::string)':
travel.cpp:43:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:43:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
