//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
 
#define y1 y114514
int T, n, m, x1, y1, x2, y2;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int f(int x, int y) {
	if((x == 1 || x == n) && (y == 1 || y == m)) return 2;
	if(x == 1 || x == n || y == 1 || y == m) return 3;
	return 4;
}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
		printf("%d\n", min(f(x1, y1), f(x2, y2)));
	}
	return 0;
}

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e3+5;
 
int T, n, k, a[N][N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d", &n, &k);
		rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]);
		int diff = 0;
		rep(i, 1, n) rep(j, 1, n) if(a[i][j] != a[n+1-i][n+1-j]) ++diff;
		diff /= 2;
		if(diff > k) puts("NO");
		else {
			k -= diff;
			if(n & 1) puts("YES");
			else if(k & 1) puts("NO");
			else puts("YES");
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int T, n, m;
 
int ask(int x, int y) {
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%d", &x);
	return x;
}
 
void give(int x, int y) {
	printf("! %d %d\n", x, y);
	fflush(stdout);
}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d", &n, &m);
		int T1 = ask(1, 1);
		if(T1 >= n) {
			int T2 = ask(1, T1+1);
			give(T2+1, T1+1);
		}
		else if(T1 >= m) {
			int T2 = ask(T1+1, 1);
			give(T1+1, T2+1);
		}
		else {
			int T2 = ask(T1+1, 1);
			int T3 = ask(1, T1+1);
			if(T2 == T1 && T3 == T1) give(T1+1, T1+1);
			else if(T3 == T1) give(T1+1, T2+1);
			else give(T3+1, T1+1);
		}
	}
	return 0;
}

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e5+5; 
 
ll n, m, a[N], sz[N], son[N], fa[N], sum[N];
vector<ll> e[N];
set<tuple<ll, ll> > sons[N]; 
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void dfs(ll u, ll f) {
	sz[u] = 1;
	sum[u] = a[u];
	fa[u] = f;
	for(auto v : e[u]) {
		if(v == f) continue;
		dfs(v, u);
		sz[u] += sz[v];
		sum[u] += sum[v];
		sons[u].insert(make_tuple(-sz[v], v));
		if(sz[v] > sz[son[u]] || sz[v] == sz[son[u]] && v < son[u]) son[u] = v;
	}
}
 
int main() {
	scanf("%lld%lld", &n, &m);
	rep(i, 1, n) scanf("%lld", &a[i]);
	rep(i, 1, n-1) {
		ll u, v;
		scanf("%lld%lld", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	while(m --> 0) {
		ll op, u;
		scanf("%lld%lld", &op, &u);
		if(op == 1) printf("%lld\n", sum[u]);
		else {
			ll v = son[u];
			if(!v) continue;
			ll p = fa[u];
			sz[u] -= sz[v];
			sum[u] -= sum[v];
			sons[u].erase(make_tuple(-sz[v], v));
			son[u] = sons[u].empty() ? 0 : get<1>(*sons[u].begin());
			fa[u] = v;
			sz[v] += sz[u];
			sum[v] += sum[u];
			sons[v].insert(make_tuple(-sz[u], u));
			son[v] = get<1>(*sons[v].begin());
			fa[v] = p;
			sons[p].erase(make_tuple(-sz[v], u));
			sons[p].insert(make_tuple(-sz[v], v));
			son[p] = get<1>(*sons[p].begin());
		}
	}
	return 0;
}

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, P = 4e5 + 5, K = 5e6 + 5, W = 5e6; 
 
int n, m, a[N], tab[K], phi[K], p[P], pcnt, dis[K], fa[K][6];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void sieve(int lim) {
	phi[1] = 1;
	rep(i, 2, lim) {
		if(!tab[i]) {
			p[++pcnt] = i;
			phi[i] = i - 1;
		}
		for(int j=1;j<=pcnt&&1LL*i*p[j]<=lim;j++) {
			tab[i*p[j]] = 1;
			if(i % p[j]) phi[i*p[j]] = phi[i] * phi[p[j]];
			else {
				phi[i*p[j]] = phi[i] * p[j];
				break;
			}
		}
	}
}
void initTree(int lim) {
	dis[1] = 1;
	rep(j, 0, 5) fa[1][j] = 1;
	rep(i, 2, lim) {
		dis[i] = dis[phi[i]] + 1;
		fa[i][0] = phi[i];
		rep(j, 1, 5) fa[i][j] = fa[fa[i][j-1]][j-1];
	}
}
int LCA(int u, int v) {
	if(dis[u] < dis[v]) swap(u, v);
	per(i, 5, 0) if(dis[fa[u][i]] >= dis[v]) u = fa[u][i];
	if(u == v) return u;
	per(i, 5, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
struct Node {
	int lca, ans, mndis, allrt;
};
struct SegTree {
	Node t[N<<2];
	#define lc(u) (u<<1)
	#define rc(u) (u<<1|1)
	void pushup(int u, int l, int r) {
		int mid = (l + r) >> 1;
		t[u].lca = LCA(t[lc(u)].lca, t[rc(u)].lca);
		t[u].ans = t[lc(u)].ans + t[rc(u)].ans
				 + (mid - l + 1) * (dis[t[lc(u)].lca] - dis[t[u].lca])
				 + (r - mid) * (dis[t[rc(u)].lca] - dis[t[u].lca]);
		t[u].mndis = min(t[lc(u)].mndis, t[rc(u)].mndis);
		t[u].allrt = t[lc(u)].allrt && t[rc(u)].allrt;
	}
	void build(int u, int l, int r) {
		if(l == r) {
			t[u].lca = a[l];
			t[u].ans = 0;
			t[u].mndis = dis[a[l]];
			t[u].allrt = a[l] == 1;
			return;
		}
		int mid = (l + r) >> 1;
		build(lc(u), l, mid);
		build(rc(u), mid+1, r);
		pushup(u, l, r);
	}
	void modify(int u, int l, int r, int ql, int qr) {
		if(t[u].allrt) return;
		if(l == r) {
			t[u].lca = fa[t[u].lca][0];
			--t[u].mndis;
			t[u].allrt = t[u].lca == 1;
			return;
		}
		int mid = (l + r) >> 1;
		if(ql <= mid) modify(lc(u), l, mid, ql, qr);
		if(qr > mid) modify(rc(u), mid+1, r, ql, qr);
		pushup(u, l, r);
	}
	int queryLCA(int u, int l, int r, int ql, int qr) {
		if(ql <= l && r <= qr) return t[u].lca;
		int mid = (l + r) >> 1;
		if(qr <= mid) return queryLCA(lc(u), l, mid, ql, qr);
		if(ql > mid) return queryLCA(rc(u), mid+1, r, ql, qr);
		int ans = queryLCA(lc(u), l, mid, ql, qr);
		if(ans == 1) return 1;
		return LCA(ans, queryLCA(rc(u), mid+1, r, ql, qr));
	}
	int queryAns(int u, int l, int r, int ql, int qr, int lca) {
		if(ql <= l && r <= qr) {
			return t[u].ans + (r - l + 1) * (dis[t[u].lca] - dis[lca]);
		}
		int mid = (l + r) >> 1, ans = 0;
		if(ql <= mid) ans += queryAns(lc(u), l, mid, ql, qr, lca);
		if(qr > mid) ans += queryAns(rc(u), mid+1, r, ql, qr, lca);
		return ans;
	}
	#undef lc
	#undef rc
}sgt;
 
int main() {
	sieve(W);
	initTree(W);
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]);
	sgt.build(1, 1, n);
	while(m --> 0) {
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1) sgt.modify(1, 1, n, l, r);
		else {
			int lca = sgt.queryLCA(1, 1, n, l, r);
			printf("%d\n", sgt.queryAns(1, 1, n, l, r, lca));
		}
	}
	return 0;
}

// Celtic
#include<bits/stdc++.h> 
#define N 501001
#define MAX 2005
using namespace std;
typedef long long ll;
typedef long double db;
const ll inf=1e18,mod=998244353,inv3=(mod+1)/3;
inline void read(ll &ret)
{
	ret=0;char c=getchar();bool pd=false;
	while(!isdigit(c)){pd|=c=='-';c=getchar();}
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
	ret=pd?-ret:ret;
	return;
}
ll n,m,x,y,siz[N],son[N],minn=inf,num=0,f[N],sum,root;
vector<ll>v[N];
bool vis[N];
inline void find(ll ver,ll fa)
{
	siz[ver]=1;
	ll maxn=0;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(to==fa||vis[to])
			continue;
		find(to,ver);
		siz[ver]+=siz[to];
		maxn=max(maxn,siz[to]);
	}
	maxn=max(maxn,num-siz[ver]);
	if(maxn<minn)
	{
		minn=maxn;
		root=ver;
	}
	return;
}
ll valmx[N],valmn[N],sz[N],now,fat[N];
struct node
{
	ll x,y,ver;
}a[N];
inline bool cmp1(node a,node b)
{
	return a.x<b.x;
}
inline bool cmp2(node a,node b)
{
	return a.y<b.y;
}
ll cnt;
vector<ll>g[N];
inline void dfs(ll ver,ll fa,ll d)
{
	valmx[ver]=max(valmx[fa],ver);
	valmn[ver]=min(valmn[fa],ver);
	if(ver!=now)
	{
		if(valmx[ver]==ver||valmx[ver]==now)
			sum++;
		if(valmn[ver]==ver||valmn[ver]==now)
			sum++;
		if(valmx[ver]==ver&&valmn[ver]==now)
			sum-=2;
		if(valmx[ver]==now&&valmn[ver]==ver)
			sum-=2;
		if(valmn[ver]==ver)
			f[now]++;
		if(valmn[ver]==now)
			f[ver]++;
		g[d].push_back(ver);
		a[++cnt]=node{valmx[ver],valmn[ver],ver};
	}
	sz[ver]=1;
	fat[ver]=d;
//	cout<<"dfs"<<ver<<" "<<fa<<" "<<d<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(to==fa||vis[to])
			continue;
		if(ver==now)
			dfs(to,ver,to);
		else
			dfs(to,ver,d);
		sz[ver]+=sz[to];
	}
	return;
}
ll tree[N];
inline void update(ll pos,ll num)
{
	pos++;
	while(pos<N)
	{
		tree[pos]+=num;
		pos+=pos&-pos;
	}
	return;
}
inline ll query(ll pos)
{
	pos++;
	ll ret=0;
	while(pos)
	{
		ret+=tree[pos];
		pos-=pos&-pos; 
	}
	return ret;
}
inline void calc()
{
	sort(a+1,a+cnt+1,cmp1);
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].x==a[k].ver)
				sum+=i-1,sum-=2*query(a[k].y)/*,cout<<"del "<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
		}
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,1);
		}
		i=j;
	}
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,-1);
		}
		i=j;
	}
	sort(a+1,a+cnt+1,cmp2);
	for(int i=cnt;i;i--)
	{
		ll j=i;
		for(;j&&a[j].y==a[i].y;j--);
		j++;
		for(int k=j;k<=i;k++)
		{
			if(a[k].y==a[k].ver)
				sum+=cnt-i;
		}
		i=j;
	}
	ll tmp=0;
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].y==a[i].y;j++);
		j--;
		for(int k=i;k<=j;k++)
			f[a[k].ver]+=tmp;
		for(int k=i;k<=j;k++)
			if(a[k].ver==a[k].y)
				tmp++;
		i=j;
	}
	return;
}
inline void decalc()
{
	sort(a+1,a+cnt+1,cmp1);
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].x==a[k].ver)
				sum-=i-1,sum+=2*query(a[k].y)/*,cout<<"back"<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
		}
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,1);
		}
		i=j;
	}
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,-1);
		}
		i=j;
	}
	sort(a+1,a+cnt+1,cmp2);
	for(int i=cnt;i;i--)
	{
		ll j=i;
		for(;j&&a[j].y==a[i].y;j--);
		j++;
		for(int k=j;k<=i;k++)
		{
			if(a[k].y==a[k].ver)
				sum-=cnt-i;
		}
		i=j;
	}
	ll tmp=0;
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].y==a[i].y;j++);
		j--;
		for(int k=i;k<=j;k++)
			f[a[k].ver]-=tmp;
		for(int k=i;k<=j;k++)
			if(a[k].ver==a[k].y)
				tmp++;
		i=j;
	}
	return;
}
inline void divide(ll ver)
{
	vis[ver]=true;
	now=ver;
	cnt=0;
	valmn[0]=inf;
	dfs(ver,0,0);
//	cout<<"??"<<ver<<" "<<sum<<endl;
/*	cout<<ver<<endl;
	for(int i=1;i<=cnt;i++)
		cout<<a[i].x<<" "<<a[i].y<<endl;*/
	calc();
//	cout<<ver<<" "<<cnt<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(vis[to])
			continue;
		cnt=0;
		for(auto x:g[to])
			a[++cnt]=node{valmx[x],valmn[x],x}/*,cout<<ver<<" "<<to<<" "<<x<<endl*/;
		g[to].clear();
	//	cout<<ver<<" "<<to<<" "<<cnt<<endl;
		decalc();
	}
//	cout<<"result::"<<ver<<" "<<sum<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(vis[to])
			continue;
		num=siz[to];
		minn=inf;
		find(to,ver);
	//	cout<<ver<<" "<<to<<" "<<root<<endl;
		divide(root);
	}
	return;
}
signed main()
{
	read(n);
	for(int i=1;i<n;i++)
	{
		read(x);
		read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	num=n;
	find(1,0);
	divide(root);
	printf("%lld\n",sum);
/*	for(int i=1;i<=n;i++)
		cout<<f[i]<<" ";
	cout<<endl;*/
	read(m);
	for(int i=1;i<=m;i++)
	{
		ll x;
		read(x);
		n++;
		f[n]=f[x]+1;
		sum+=(n-1)-f[n];
		printf("%lld\n",sum);
	}
	exit(0);
}

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 4e5+5;
 
ll n, m, k, faMx[N], faMn[N], disMx[N], disMn[N], dfn[N], sz[N], tms;
ll A, B, C, ans;
vector<ll> eMx[N], eMn[N], reMx[N], reMn[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Dsu {
	ll fa[N];
	void init(ll x) {rep(i, 1, x) fa[i] = i;}
	ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	bool merge(ll x, ll y) {
		ll u = find(x), v = find(y);
		if(u == v) return 0;
		fa[u] = v;
		return 1;
	}
}dsu;
struct BIT {
	ll c[N], sz;
	void init(ll x) {sz = x; rep(i, 1, x) c[i] = 0;}
	ll lowbit(ll x) {return x & (-x);}
	void add(ll x, ll k) {for(; x <= sz; x += lowbit(x)) c[x] += k;}
	ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
	ll Ask(ll x, ll y) {return ask(y) - ask(x - 1);}
}bit;
void dfs1(ll u) {
	dfn[u] = ++tms;
	sz[u] = 1;
	disMx[u] = disMx[faMx[u]] + 1;
	B += disMx[u] - 1;
	for(ll v : reMx[u]) {
		dfs1(v);
		sz[u] += sz[v];
	}
}
void dfs2(ll u) {
	disMn[u] = disMn[faMn[u]] + 1;
	A += disMn[u] - 1;
	C += bit.Ask(dfn[u], dfn[u] + sz[u] - 1);
	bit.add(dfn[u], 1);
	for(ll v : reMn[u]) dfs2(v);
	bit.add(dfn[u], -1);
}
 
int main() {
	scanf("%lld", &n);
	rep(i, 1, n-1) {
		ll u, v;
		scanf("%lld%lld", &u, &v);
		if(u < v) swap(u, v);
		eMx[u].push_back(v);
		eMn[v].push_back(u);
	}
	dsu.init(n);
	rep(i, 1, n) {
		for(ll j : eMx[i]) {
			j = dsu.find(j);
			dsu.merge(j, i);
			faMx[j] = i;
			reMx[i].push_back(j);
		}
	}
	dsu.init(n);
	per(i, n, 1) {
		for(ll j : eMn[i]) {
			j = dsu.find(j);
			dsu.merge(j, i);
			faMn[j] = i;
			reMn[i].push_back(j);
		}
	}
	bit.init(n);
	dfs1(n);
	dfs2(1);
	ans = A + B - 2 * C;
	// printf("%lld + %lld - 2 * %lld = %lld\n", A, B, C, ans);
	printf("%lld\n", ans);
	for(scanf("%lld", &m); m; m--) {
		scanf("%lld", &k);
		disMn[++n] = disMn[k] + 1;
		ans += n - disMn[n];
		printf("%lld\n", ans);
	}
	return 0;
}