#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define sp <<' '<<
#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define carp(a,b) ((a%MOD)*(b%MOD))%MOD
#define topla(a,b) ((a%MOD)+(b%MOD))%MOD
#define pb push_back
#define DEBUG(x) cout<<#x sp x<<endl;
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
const int MAXN=2e3+6;
const int INF=1e9+7;
#include "werewolf.h"
int n,q;
vi adj[MAXN];
vi vec;
bool vis[MAXN];
void dfs(int nd){
vec.pb(nd);
vis[nd]=true;
for(auto kom:adj[nd]){
if(!vis[kom]) dfs(kom);
}
}
vi t[MAXN*4];
vi mn[MAXN*4]; //mn[i] --> [1,i] min indis
deque<int> mx[MAXN*4]; //mx[i] --> [i,n] max indis
int yer[MAXN];
void merge(vi &a,vi &b,vi &c,vi& d,deque<int>& e){
int sz1=a.size();
int sz2=b.size();
int p1,p2;
p1=p2=0;
int cur=INF;
while(p1<sz1 or p2<sz2){
if(p1>=sz1 or (p2<sz2 and a[p1]>=b[p2])){
cur=min(cur,yer[b[p2]]);
c.pb(b[p2++]);
}
else{
cur=min(cur,yer[a[p1]]);
c.pb(a[p1++]);
}
d.pb(cur);
}
int cur2=-INF;
for(int i=c.size()-1;i>=0;i--){
cur2=max(cur2,yer[c[i]]);
e.push_front(cur2);
}
}
void build(int nd=1,int l=1,int r=n){
if(l==r){
cout<<"build"<<endl;
t[nd].pb(vec[l]);
mn[nd].pb(l);
mx[nd].pb(l);
return;
}
build(nd*2,l,mid);
build(nd*2+1,mid+1,r);
merge(t[nd*2],t[nd*2+1],t[nd],mn[nd],mx[nd]);
}
int val,f;
int bir,iki;
/*
f=1 --> valdan küçük ilk elemanı bul
f=2 --> valdan büyük son elemanı bul
*/
void qu(int ql,int qr,int nd=1,int l=1,int r=n){
if(l>r or l>qr or r<ql) return;
if(ql<=l and r<=qr){
if(f){
auto ind=upper_bound(all(t[nd]),val)-t[nd].begin();
if(ind){
ind--;
bir=min(bir,mn[nd][ind]-1);
}
}
else{
auto ind=upper_bound(all(t[nd]),val)-t[nd].begin();
if(ind<t[nd].size()){
iki=max(iki,mx[nd][ind]+1);
}
}
return;
}
qu(ql,qr,nd*2,l,mid);
qu(ql,qr,nd*2+1,mid+1,r);
}
vi check_validity(int N, vi x, vi y, vi S, vi E, vi L, vi R){
//line
n=N;
FOR(i,n){
x[i]++;y[i]++;
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
q=S.size();
vec.pb(0);
FORE(i,1,n+1){
if(adj[i].size()==1){
//baslangıc
dfs(i);
}
}
FORE(i,1,n+1){
yer[vec[i]]=i;
}
build();
vi ans;
FOR(i,q){
int bas=yer[S[i]+1];
int son=yer[E[i]+1];
if(bas>son) swap(bas,son);
int l=L[i]+1;
int r=R[i]+1;
bir=n;iki=1;
val=l;f=1;
qu(bas,son);
val=r;f=0;
qu(bas,son);
if(bir<iki) ans.pb(0);
else ans.pb(1);
}
return ans;
/*int Q = S.size();
vi A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
return A;*/
}
