{"problem":{"name":"Tree and Constraints","description":{"content":"We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$.   Consider painting each of these edges white or black. There are $2^{N-1}$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc152_f"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$.  \nConsider painting each of these edges white or black. There are $2^{N-1}$ such ways to paint the edges. Among them, how many satisfy all of the following $M$ restrictions?\n\n*   The $i$\\-th $(1 \\leq i \\leq M)$ restriction is represented by two integers $u_i$ and $v_i$, which mean that the path connecting Vertex $u_i$ and Vertex $v_i$ must contain at least one edge painted black.\n\n## Constraints\n\n*   $2 \\leq N \\leq 50$\n*   $1 \\leq a_i,b_i \\leq N$\n*   The graph given in input is a tree.\n*   $1 \\leq M \\leq \\min(20,\\frac{N(N-1)}{2})$\n*   $1 \\leq u_i < v_i \\leq N$\n*   If $i \\not= j$, either $u_i \\not=u_j$ or $v_i\\not=v_j$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$:$\n$a_{N-1}$ $b_{N-1}$\n$M$\n$u_1$ $v_1$\n$:$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc152_f","tags":[],"sample_group":[["3\n1 2\n2 3\n1\n1 3","3\n\nThe tree in this input is shown below:  \n  \n![image](https://img.atcoder.jp/ghi/5b0208ab1e3bb39a5d4fb7bafbfc448e.png)  \n  \nAll of the $M$ restrictions will be satisfied if Edge $1$ and $2$ are respectively painted (white, black), (black, white), or (black, black), so the answer is $3$."],["2\n1 2\n1\n1 2","1\n\nThe tree in this input is shown below:  \n  \n![image](https://img.atcoder.jp/ghi/d08b3f53dfa4857fe9ffe13fa5d7ae69.png)  \n  \nAll of the $M$ restrictions will be satisfied only if Edge $1$ is painted black, so the answer is $1$."],["5\n1 2\n3 2\n3 4\n5 3\n3\n1 3\n2 4\n2 5","9\n\nThe tree in this input is shown below:  \n  \n![image](https://img.atcoder.jp/ghi/386502bb3c85e0bb5aee64e4e7c087a1.png)"],["8\n1 2\n2 3\n4 3\n2 5\n6 3\n6 7\n8 6\n5\n2 7\n3 5\n1 6\n2 8\n7 8","62\n\nThe tree in this input is shown below:  \n  \n![image](https://img.atcoder.jp/ghi/955fa8fd8af658abb24ff2f68b9997be.png)"]],"created_at":"2026-03-03 11:01:13"}}