You are given a tree consisting of n vertices, and m simple vertex paths. Your task is to find how many pairs of those paths intersect at exactly one vertex. More formally you have to find the number of pairs (i, j) (1 ≤ i < j ≤ m) such that path_i and path_j have exactly one vertex in common. 

Input

First line contains a single integer n (1 ≤ n ≤ 3 ⋅ 10^5).

Next n - 1 lines describe the tree. Each line contains two integers u and v (1 ≤ u, v ≤ n) describing an edge between vertices u and v.

Next line contains a single integer m (1 ≤ m ≤ 3 ⋅ 10^5).

Next m lines describe paths. Each line describes a path by it's two endpoints u and v (1 ≤ u, v ≤ n). The given path is all the vertices on the shortest path from u to v (including u and v).

Output

Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

Examples

Input


5
1 2
1 3
1 4
3 5
4
2 3
2 4
3 4
3 5


Output


2


Input


1
3
1 1
1 1
1 1


Output


3


Input


5
1 2
1 3
1 4
3 5
6
2 3
2 4
3 4
3 5
1 1
1 2


Output


7

Note

<image>

The tree in the first example and paths look like this. Pairs (1,4) and (3,4) intersect at one vertex.

In the second example all three paths contain the same single vertex, so all pairs (1, 2), (1, 3) and (2, 3) intersect at one vertex.

The third example is the same as the first example with two additional paths. Pairs (1,4), (1,5), (2,5), (3,4), (3,5), (3,6) and (5,6) intersect at one vertex.
// PRAGMAS
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

// INCLUDES
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;

// DEFINES
// #define int               long long
#define mp                make_pair
#define pb                push_back
#define eb                emplace_back
#define ins               insert
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define inparr(x,n)       for(int _i = 0; _i < (n); ++_i)cin>>(x)[_i];
#define popcnt            __builtin_popcountll
#define elasped_time      1.0 * clock() / CLOCKS_PER_SEC 

// TYPEDEFS
using ll = long long;
using str = string;
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
template<class T> using vec = vector<T>;

// I/O
void setPrec(int prec) { cout << fixed << setprecision(prec); }
void unsyncIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }

// INPUT
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}

template<class T, class U> void read(pair<T,U>& p);
template<class T> void read(vector<T>& v);

template<class T> void read(T& x) { cin >> x; }
void read(double& d) { str t; read(t); d = stod(t); }
void read(long double& d) { str t; read(t); d = stold(t); }
template<class T, class ...U> void read(T& t, U&... u) { read(t); read(u...); }
template<class T, class U> void read(pair<T,U>& p) { read(p.fr,p.sc); }
template<class T> void read(vector<T>& x) { for(auto &z: x) read(z); }
template<class T> void readn(vector<T>& x, int n) { x.resize(n); for(auto &z: x) read(z); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}

template<size_t SZ> str ts(bitset<SZ> b) { str res = ""; for(int i = 0; i < SZ; ++i) res += char('0'+b[i]); return res; }
template<class T, class U> str ts(pair<T,U> p);
template<class T> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
	#endif
}

template<class T, class U> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.fr)+", "+ts(p.sc)+")"; 
	#else
		return ts(p.fr)+" "+ts(p.sc);
	#endif
}
 
// OUTPUT
template<class T> void pr(T x) { cout << ts(x); }
template<class T, class ...U> void pr(const T& t, const U&... u) { pr(t); pr(u...); }
void write() { pr("\n"); } // print w/ spaces
template<class T, class ...U> void write(const T& t, const U&... u) { 
	pr(t); if (sizeof...(u)) pr(" "); write(u...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class T,class ...U> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

// MISC
template<class T> int lwb(vector<T>& a, const T& b) { return lower_bound(all(a),b)-(a).begin(); }
template<class T> void uniq(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),v.end()); }

// template<typename T>
// using oset = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const long long inf = 1e18;
const int hell = 1e9+7; // 998244353;
const long double PI = acos((long double)-1);
const int maxn = 3*100005;

const int H = 19;
int par[maxn][H+1], lvl[maxn];
vi adj[maxn];
void dfs(int z, int p){
	lvl[z] = lvl[p] + 1;
	par[z][0] = p;
	for (int i = 1; i <= H; ++i){
		par[z][i] = par[par[z][i-1]][i-1];
	}
	for(int x:adj[z]){
		if(x==p)continue;
		dfs(x,z);
	}
}

int lca(int x, int y) {
	if (lvl[x] < lvl[y]) swap(x, y);
	for (int i = H; i >= 0; i--){
		if (lvl[x] - (1<<i) >= lvl[y]){
			x = par[x][i];
		}
	}
	if (x == y) return x;
	for (int i = H; i >= 0; i--){
		if (par[x][i] != par[y][i]){
			x = par[x][i], y = par[y][i];
		}
	}
	return par[x][0];
}

int lvlanc(int x, int dep) {
	for (int i = H; i >=0 ; --i) {
		if (lvl[x] - (1<<i) >= dep) {
			x = par[x][i];
		}
	}
	return x;
}
vii paths;
vi cat[maxn];

int pathsgoing[maxn];
int standup[maxn];
void ddfs(int v, int par) {
	for(auto u:adj[v]) {
		if (u!= par) {
			ddfs(u, v);
			pathsgoing[v] += pathsgoing[u];
		}
	}
}
void solve(){
	int n;
	read(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		read(u, v);
		adj[u].pb(v);		
		adj[v].pb(u);		
	}
	dfs(1, 0);
	int m;
	read(m);
	for (int i = 0; i < m; ++i) {
		int u, v;
		read(u, v);
		paths.eb(u, v);
		int pp = lca(u, v);
		if (pp != u) {
			standup[u] ++;
		}
		if (pp != v) {
			standup[v] ++;
		}
		pathsgoing[u]++;
		pathsgoing[v]++;
		pathsgoing[pp]-=2;
		cat[pp].pb(i);
	}
	// count paths going through a node
	ddfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		dbg(i, pathsgoing[i]);
	}
	long long ans = 0, res = 0;
	for (int i = 1; i <= n; ++i) {
		map<pii,long long> cnt;
		map<int,long long> cnt2;
		for (auto idx : cat[i]) {
			int c1 = 0, c2 = 0;
			if (paths[idx].fr != i) {
				c1 = lvlanc(paths[idx].fr, lvl[i] + 1);
			}
			if (paths[idx].sc != i) {
				c2 = lvlanc(paths[idx].sc, lvl[i] + 1);
			}
			if (c1 > c2) {
				swap(c1, c2);
			}
			cnt[{c1, c2}]++;
			cnt2[c1]++;
			cnt2[c2]++;
		}
		// count paths with intersection at common lca
		// intersection with single vertex i
		ans += cnt[{0,0}] * (cnt[{0,0}] - 1) + cnt[{0,0}]*(sz(cat[i]) - cnt[{0, 0}]);
		// intersection with vertical ending at i
		for (auto u : cnt) {
			if (u.fr.fr == 0 && u.fr.sc != 0) {
				ans += u.sc * (sz(cat[i]) - cnt2[u.fr.sc]);
			}
		}
		// intersection with up-down
		for (auto u : cnt) {
			if (u.fr.fr != 0 && u.fr.sc != 0) {
				ans += u.sc * sz(cat[i]);
				ans -= u.sc * (cnt2[u.fr.sc]);
				ans -= u.sc * (cnt2[u.fr.fr]);
				ans += u.sc * cnt[u.fr];
			}
		}
		// count paths with intersection at lca of one path and other path going up 
		for (auto u : adj[i]) {
			if (lvl[u] < lvl[i]) continue;
			res += (pathsgoing[u] - cnt2[u])*(sz(cat[i]) - cnt2[u]);
			dbg(res, i, u, pathsgoing[u] - cnt2[u]);
		}
		res += standup[i]*(sz(cat[i]));
	}
	dbg(ans, res);
	write(ans / 2 + res);
	
}

signed main(){
	unsyncIO();
	// setPrec(9);
	// setIn("input.txt");
	// setOut("output.txt");
	int cases=1;
	//cin>>cases;
	for (int i = 1; i <= cases; ++i) {
		solve();
	}
	#ifdef LOCAL
	    cerr<<endl<<"Time Elasped : "<<elasped_time<<endl;
	#endif
	return 0;
}
