Lexicographically Smallest Perfect Orientation

Given a tree with \(n\) vertices numbered from \(1\) to \(n\) and \(n-1\) edges. The \(i\)-th edge connects vertices \(u_i\) and \(v_i\). We want to assign a direction for every edge. An orientation can be described by a binary string \(S=s_1s_2\ldots s_{n-1}\) of length \(n-1\) where:

• If \(s_i=0\), then the \(i\)-th edge is oriented as \(u_i\to v_i\).
• If \(s_i=1\), then the \(i\)-th edge is oriented as \(v_i\to u_i\).

There are \(m\) given vertex pairs \((a_i, b_i)\) (with \(a_i\neq b_i\)). An orientation is called a perfect orientation if for every given pair \((a_i,b_i)\), there is no directed path from \(a_i\) to \(b_i\) under this orientation.

For any two binary strings \(S\) and \(T\) of length \(n-1\), we say \(S\) is lexicographically smaller than \(T\) if there exists an index \(k\) such that \(s_1 = t_1, s_2 = t_2, \ldots, s_{k-1}= t_{k-1}\) and \(s_k < t_k\).

Your task is to find, among all perfect orientations, the one whose corresponding binary string is lexicographically smallest. It is guaranteed that there exists at least one perfect orientation.

Note on the Path Condition

For any pair \((a,b)\), there is a unique simple undirected path in the tree. Let the edges on this path be \(e_1,e_2,\ldots,e_k\). If, when traversing from \(a\) to \(b\), the edge \(e_j\) is traversed in the same direction as the default orientation (i.e. if \(e_j\) is defined as \(u\to v\) and it is used from \(u\) to \(v\) on the path) then the expected bit for that edge is 0; otherwise the expected bit is 1. A directed path from \(a\) to \(b)\ exists if and only if for every edge on the path, the assigned bit agrees with the expected bit. In our default assignment we consider all bits to be 0. Thus a query \((a,b)\) is satisfied by the default assignment if there exists at least one edge on the path for which the expected bit is 1. For those queries for which every edge has expected bit 0 the default assignment would yield a directed path. To avoid that, we must flip at least one edge (i.e. assign 1 instead of 0) on such a path. To preserve lexicographical minimality we want to postpone flips as late as possible (i.e. choose an edge with as high an index as possible in the binary string).

It can be shown that if you, for every query whose unique path has expected bit 0 for every edge, pick the edge with the maximum index on that path and flip it, then the resulting binary string is lexicographically smallest among all perfect orientations.

inputFormat

The input is given as follows:

 n
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)
 m
 a1 b1
 a2 b2
 ...
 am bm

It is guaranteed that the given graph is a tree and \(1 \leq u_i,v_i,a_i,b_i \leq n\) and \(a_i\neq b_i\).

outputFormat

Output a binary string \(S=s_1s_2\ldots s_{n-1}\) corresponding to the lexicographically smallest perfect orientation.

sample

3
1 2
2 3
1
1 3

01