Minimum Number of Servers to Disable Applications

You are given a network of \( n \) servers connected by \( n-1 \) bidirectional cables. The \( i\)th cable connects servers \( u_i \) and \( v_i \); it is guaranteed that the network is connected, i.e. for every pair of servers \( i \) and \( j \) there is a path between them.

There are \( m \) applications running on the network. The \( j\)th application runs on two designated servers \( a_j \) and \( b_j \). Initially, all servers are active (running).

An application \( j \) will continue to run if either of the following conditions holds:

• Both servers \( a_j \) and \( b_j \) are active.
• There is a path between \( a_j \) and \( b_j \) that uses only active servers.

You are to choose a set of servers to stop (i.e. disable) such that every application is disabled. An application is disabled if both conditions above are false. In other words, for every application, the unique path in the tree between \( a_j \) and \( b_j \) must contain at least one disabled server. Find the minimum number of servers that need to be stopped in order to disable all applications.

Note: Since the network forms a tree, there is exactly one simple path between any two servers. For an application \( j \), if we denote the set of servers along the unique path from \( a_j \) to \( b_j \) (including \( a_j \) and \( b_j \)) by \( P_j \), then you must choose at least one server from \( P_j \) to disable.

inputFormat

The first line contains a single integer \( n \) (the number of servers).

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) representing a bidirectional cable connecting servers \( u \) and \( v \).

The next line contains a single integer \( m \) (the number of applications).

Each of the next \( m \) lines contains two integers \( a_j \) and \( b_j \) indicating that the \( j\)th application runs on servers \( a_j \) and \( b_j \).

It is guaranteed that the given graph is a tree and \( 1 \leq u,v,a_j,b_j \leq n\).

outputFormat

Output a single integer: the minimum number of servers that need to be stopped such that all applications are disabled.

sample

3
1 2
2 3
1
1 3

1