#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) cout<<#v<<' '; for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 255;
int start[mxn];
int finish[mxn];
int timer = 0;
vvi adj(mxn);
vb vis(mxn);
vi dfs_order;
vi depth(mxn);
vi par(mxn);
void euler_tour(int x, int from){
//dfs_order.pb(x);
par[x] = from;
if(x != 1)depth[x] = depth[from] + 1;
//timer++;
//start[x] = timer;
for(auto u : adj[x]){
if(u != from)euler_tour(u, x);
dfs_order.pb(x);
}
//finish[x] = timer;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin(".in");
//ofstream cout(".out");
int tt;
cin>>tt;
f0r(ttt, tt){
in(n);
FOR(i, 1, n+1)adj[i].clear();
f0r(i,n-1){
in2(a,b);
adj[a].pb(b);
adj[b].pb(a);
}
in(m);
if(tt <= 20 && n <= 250 && m <= 100){
FOR(i, 1, n+1)vis[i] = 0;
FOR(i, 1, n+1)depth[i] = 0;
FOR(i, 1, n+1)par[i] = -1;
dfs_order.clear();
vpii paths;
f0r(i, m){
in2(a,b);
paths.pb({a,b});
}
euler_tour(1, -1);
//vout(depth);
//vout(par);
//vout(dfs_order);
/*
vi loc(n+1);
f0r(i, n){
loc[dfs_order[i]] = i;
}
int spt[n][10];
f0r(i,n)spt[i][0] = depth[dfs_order[i]];
FOR(j, 1, 10){
f0r(i, n - (1 << j) + 1){
spt[i][j] = min(spt[i][j-1], spt[i + (1 << (j-1))][j-1]);
}
}
*/
bool ans = 1;
//vout(depth);
//vout(par);
f0r(i, m){
FOR(j, i+1, m){
//construct path i
int s1 = paths[i].first;
int e1 = paths[i].second;
/*
int lg = floor(log2(e1 - s1 + 1));
int mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
*/
//dout(mnd);
vi p1;
vi tmp;
while(depth[s1] != depth[e1]){
if(depth[s1] > depth[e1]){
p1.pb(s1);
s1 = par[s1];
}
else{
tmp.pb(e1);
e1 = par[e1];
}
}
while(s1 != e1){
p1.pb(s1);
tmp.pb(e1);
s1 = par[s1];
e1 = par[e1];
}
p1.pb(s1);
reverse(all(tmp));
for(auto u : tmp)p1.pb(u);
//construct path j
s1 = paths[j].first;
e1 = paths[j].second;
/*
int lg = floor(log2(e1 - s1 + 1));
int mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
*/
//dout(mnd);
vi p2;
vi tmp2;
while(depth[s1] != depth[e1]){
if(depth[s1] > depth[e1]){
p2.pb(s1);
s1 = par[s1];
}
else{
tmp2.pb(e1);
e1 = par[e1];
}
}
while(s1 != e1){
p2.pb(s1);
tmp2.pb(e1);
s1 = par[s1];
e1 = par[e1];
}
p2.pb(s1);
reverse(all(tmp2));
for(auto u : tmp2)p2.pb(u);
//vout(p1);
//vout(p2);
//now check if the paths are ok
vector<set<int>> deg(n+1);
f0r(k, p1.size() - 1){
deg[p1[k]].insert(p1[k+1]);
deg[p1[k+1]].insert(p1[k]);
}
f0r(k, p2.size() - 1){
deg[p2[k]].insert(p2[k+1]);
deg[p2[k+1]].insert(p2[k]);
}
bool branch = 0;
f0r(k, n+1){
//cout<<deg[k].size()<<' ';
if(deg[k].size() > 2)branch = 1;
}
//cout<<'\n';
if(!branch){
if(find(all(p1), p2[0]) != p1.end() && find(all(p1), p2[p2.size() - 1]) != p1.end()){
ans = 0;
}
else{
vi nxt(n+1);
f0r(k, p1.size() - 1){
nxt[p1[k]] = p1[k+1];
}
//vout(nxt);
f0r(k, p2.size() - 1){
if(nxt[p2[k+1]] == p2[k])ans = 0;
}
}
}
}
}
yn(ans);
}
else{
vpii v;
vector<pair<pii,int>>w;
f0r(i,m){
in2(a,b);
v.pb({min(a,b),max(a,b)});
w.pb({{min(a,b),max(a,b)}, (a > b)});
}
sort(all(v));
sort(all(w));
int mx = -1;
bool ok = 1;
f0r(i,m){
//out3(w[i].first.first, w[i].first.second, w[i].second);
}
f0r(i,m){
if(v[i].second <= mx){
ok = 0;
break;
}
else{
mx = v[i].second;
}
}
mx = -1;
int mx2 = -1;
f0r(i, m){
if(w[i].second){
if(w[i].first.first < mx)ok = 0;
else mx2 = w[i].first.second;
}
else{
if(w[i].first.first < mx2)ok = 0;
else mx = w[i].first.second;
}
}
yn(ok);
}
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
173 | f0r(k, p1.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:173:6: note: in expansion of macro 'f0r'
173 | f0r(k, p1.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
177 | f0r(k, p2.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:177:6: note: in expansion of macro 'f0r'
177 | f0r(k, p2.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
194 | f0r(k, p1.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:194:8: note: in expansion of macro 'f0r'
194 | f0r(k, p1.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
198 | f0r(k, p2.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:198:8: note: in expansion of macro 'f0r'
198 | f0r(k, p2.size() - 1){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
416 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
13 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
416 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
13 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
