트리와 쿼리

$1$부터 $N$까지 $N$개의 정점으로 이루어진 트리가 있다. $i$번째 간선은 서로 다른 두 정점 $A_i$, $B_i$를 잇는다. ($1 ≤ i ≤ N - 1$)

$N$개의 정점 중 몇 개를 골라, 그 고른 정점들을 $S = \{s_1, s_2, \dots , s_K\}$라고 하자. 또한, $s_i = v$를 만족하는 $i$ ($1 ≤ i ≤ K$)가 존재할 때, 정점 $v$가 $S$에 속한다고 부르자.

$S$에 속하는 서로 다른 두 정점 $u$, $v$에 대하여, $S$에 속하는 정점만을 이용하여 트리 위에서 $u$, $v$ 사이를 오갈 수 있다면, “$u$와 $v$는 $S$ 위에서 연결되어 있다”고 하자.

예를 들어, 아래와 같은 트리를 생각하자. ($N = 7$)

만일, $K = 6$, $S = \{1, 2, 3, 4, 5, 6\}$라면, “$1$과 $2$”, “$3$과 $5$”, “$4$와 $6$”은 각각 서로 $S$ 위에서 연결되어 있다. 그러나, “$1$과 $6$”, “$2$와 $7$”은 각각 서로 $S$ 위에서 연결되어 있지 않다.

다음 조건을 모두 만족하는 정점쌍 $(u, v)$의 개수를 $S$의 연결 강도라고 하자.

1. $u$와 $v$는 서로 다른 두 정점.
2. $1 ≤ u < v ≤ N$.
3. $u$와 $v$는 $S$ 위에서 연결되어 있다.

고른 정점들 $S$가 주어질 때, $S$의 연결 강도를 계산하는 프로그램을 작성하라. 여러분은 이러한 질의 $Q$개에 대하여 모두 답해야 한다.

Limit

• $2 ≤ N ≤ 250\,000$
• $1 ≤ Q ≤ 100\,000$
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $1 ≤ A_i ≤ N$.
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $1 ≤ B_i ≤ N$.
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $A_i ≠ B_i$.
• 주어지는 그래프는 트리이다.
• 모든 질의에 대해, $1 ≤ K ≤ N$.
• 각 질의에서, 모든 $i$ ($1 ≤ i ≤ K$)에 대해, $1 ≤ s_i ≤ N$.
• 각 질의에서, 고른 $K$개의 정점 $s_1, \dots , s_K$는 서로 다르다.
• $Q$개의 질의에서 주어지는 $K$들의 합은 $1\,000\,000$ 이하이다.

Subtask

Lang Base64

W3sicHJvYmxlbV9pZCI6IjI1NDAyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjXHVjNjQwIFx1Y2ZmY1x1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+JDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNzg4XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVhYzA0XHVjMTIwXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzgxNVx1YzgxMCAkQV9pJCwgJEJfaSRcdWI5N2MgXHVjNzg3XHViMjk0XHViMmU0LiAoJDEgJmxlOyBpICZsZTsgTiAtIDEkKTxcL3A+XHJcblxyXG48cD4kTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwIFx1YzkxMSBcdWJhODcgXHVhYzFjXHViOTdjIFx1YWNlOFx1Yjc3YywgXHVhZGY4IFx1YWNlMFx1Yjk3OCBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NDQgJFMgPSBcXHtzXzEsIHNfMiwgXFxkb3RzICwgc19LXFx9JFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YjYxMFx1ZDU1YywgJHNfaSA9IHYkXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAkaSQgKCQxICZsZTsgaSAmbGU7IEskKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHViNTRjLCBcdWM4MTVcdWM4MTAgJHYkXHVhYzAwICRTJFx1YzVkMCBcdWMxOGRcdWQ1NWNcdWIyZTRcdWFjZTAgXHViZDgwXHViOTc0XHVjNzkwLjxcL3A+XHJcblxyXG48cD4kUyRcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzgxNVx1YzgxMCAkdSQsICR2JFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsICRTJFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHVjODE1XHVjODEwXHViOWNjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWQyYjhcdWI5YWMgXHVjNzA0XHVjNWQwXHVjMTFjICR1JCwgJHYkIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM2MjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgJmxkcXVvOyR1JFx1YzY0MCAkdiRcdWIyOTQgJFMkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0JnJkcXVvO1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkMmI4XHViOWFjXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC4gKCROID0gNyQpPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNzE4ZTdjNmQtYjcxOC00NWEwLTg0YjctMGVkNjdiZDAxYzIyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNTlweDsgaGVpZ2h0OiAxNDVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNzdjLCAkSyA9IDYkLCAkUyA9IFxcezEsIDIsIDMsIDQsIDUsIDZcXH0kXHViNzdjXHViYTc0LCAmbGRxdW87JDEkXHVhY2ZjICQyJCZyZHF1bzssICZsZHF1bzskMyRcdWFjZmMgJDUkJnJkcXVvOywgJmxkcXVvOyQ0JFx1YzY0MCAkNiQmcmRxdW87XHVjNzQwIFx1YWMwMVx1YWMwMSBcdWMxMWNcdWI4NWMgJFMkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTgsICZsZHF1bzskMSRcdWFjZmMgJDYkJnJkcXVvOywgJmxkcXVvOyQyJFx1YzY0MCAkNyQmcmRxdW87XHVjNzQwIFx1YWMwMVx1YWMwMSBcdWMxMWNcdWI4NWMgJFMkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1YzMwZCAkKHUsIHYpJFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgJFMkXHVjNzU4IFx1YzVmMFx1YWNiMCBcdWFjMTVcdWIzYzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPiR1JFx1YzY0MCAkdiRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjODE1XHVjODEwLjxcL2xpPlxyXG5cdDxsaT4kMSAmbGU7IHUgJmx0OyB2ICZsZTsgTiQuPFwvbGk+XHJcblx0PGxpPiR1JFx1YzY0MCAkdiRcdWIyOTQgJFMkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YWNlMFx1Yjk3OCBcdWM4MTVcdWM4MTBcdWI0ZTQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsICRTJFx1Yzc1OCBcdWM1ZjBcdWFjYjAgXHVhYzE1XHViM2M0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzljOFx1Yzc1OCAkUSRcdWFjMWNcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIFx1YmFhOFx1YjQ1MCBcdWIyZjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAoJE4gLSAxJClcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgJGkkICgkMSAmbGU7IGkgJmxlOyBOIC0gMSQpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICRBX2kkLCAkQl9pJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICRRJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWM5YzhcdWM3NThcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgJGkkICgkMSAmbGU7IGkgJmxlOyBRJClcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwICRpJFx1YmM4OFx1YzlmOCBcdWM5YzhcdWM3NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWM4MTVcdWMyMTggJEskXHVjNjQwICRLJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJHNfMSwgXFxkb3RzICwgc19LJFx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWFjMDEgXHVjOWM4XHVjNzU4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjOTExICRpJCAoJDEgJmxlOyBpICZsZTsgUSQpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHVjOWM4XHVjNzU4XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCAkUyRcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjLCAkUyRcdWM3NTggXHVjNWYwXHVhY2IwIFx1YWMxNVx1YjNjNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyICZsZTsgTiAmbGU7IDI1MFxcLDAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgJmxlOyBRICZsZTsgMTAwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgJGkkICgkMSAmbGU7IGkgJmxlOyBOIC0gMSQpXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJDEgJmxlOyBBX2kgJmxlOyBOJC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwICRpJCAoJDEgJmxlOyBpICZsZTsgTiAtIDEkKVx1YzVkMCBcdWIzMDBcdWQ1NzQsICQxICZsZTsgQl9pICZsZTsgTiQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCAkaSQgKCQxICZsZTsgaSAmbGU7IE4gLSAxJClcdWM1ZDAgXHViMzAwXHVkNTc0LCAkQV9pICZuZTsgQl9pJC48XC9saT5cclxuXHQ8bGk+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWM5YzhcdWM3NThcdWM1ZDAgXHViMzAwXHVkNTc0LCAkMSAmbGU7IEsgJmxlOyBOJC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YzljOFx1Yzc1OFx1YzVkMFx1YzExYywgXHViYWE4XHViNGUwICRpJCAoJDEgJmxlOyBpICZsZTsgSyQpXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJDEgJmxlOyBzX2kgJmxlOyBOJC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YzljOFx1Yzc1OFx1YzVkMFx1YzExYywgXHVhY2UwXHViOTc4ICRLJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTAgJHNfMSwgXFxkb3RzICwgc19LJFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kUSRcdWFjMWNcdWM3NTggXHVjOWM4XHVjNzU4XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCAkSyRcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzQwICQxXFwsMDAwXFwsMDAwJCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROID0gMyQuPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiAmbGU7IDUwJCwgJFEgJmxlOyA1MCQuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiAmbGU7IDJcXCw1MDAkLCAkUSAmbGU7IDJcXCw1MDAkLjxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+XHVhYzAxIFx1YzljOFx1Yzc1OFx1YzVkMFx1YzExYywgJEsgPSAzJC48XC9wPlxyXG4iLCJzdWJ0YXNrNSI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0Yy48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyNTQwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZXJ5IG9uIGEgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHRyZWUgd2hlcmUgdmVydGljZXMgYXJlIGxhYmVsZWQgd2l0aCBpbnRlZ2VycyAkMSwgMiwgXFxsZG90cywgTiQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhIHN1YnNldCBvZiB2ZXJ0aWNlcyAkUyBcXHN1YnNldGVxIFxcezEsIDIsIFxcbGRvdHMsIE5cXH0kLCB3ZSBzYXkgdHdvIHZlcnRpY2VzICQodSwgdikkIGFyZSA8ZW0+Y29ubmVjdGVkIHVuZGVyPFwvZW0+Jm5ic3A7JFMkIGlmIHRoZXJlIGV4aXN0cyBhIHBhdGggdGhhdCBvbmx5IHBhc3NlcyB0aHJvdWdoIHRoZSB2ZXJ0aWNlcyBpbiAkUyQuIE5vdGUgdGhhdCB0aGlzIGluY2x1ZGVzIGVuZHBvaW50cyBvZiB0aGUgcGF0aCwgc28gJHUsIHYgXFxpbiBTJCBzaG91bGQgaG9sZC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgdHJlZSBhbmQgdGhlIHNldCAkUyA9IFxcezEsIDIsIDMsIDQsIDUsIDZcXH0kLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzAwNTA3YTZlLWIyN2ItNGE5Mi1iM2QzLWYyY2ExOGI4Nzc1MFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjU5cHg7IGhlaWdodDogMTQ1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoaXMgY2FzZSwgJCgxLCAyKSQsICQoMywgNSkkIGFuZCAkKDQsIDYpJCBhcmUgY29ubmVjdGVkIHVuZGVyICRTJCwgd2hpbGUgJCgxLCA2KSQgYW5kICQoMiwgNykkIGFyZSBub3QgY29ubmVjdGVkIHVuZGVyfiRTJC48XC9wPlxyXG5cclxuPHA+TGV0ICRcXG1hdGhpdHtzdHJlbmd0aH0oUykkIGJlIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgdmVydGljZXMgJCh1LCB2KSQgc3VjaCB0aGF0ICR1IFxcbmVxIHYkIGFuZCAkKHUsIHYpJCBhcmUgY29ubmVjdGVkIHVuZGVyICRTJC4gWW91IGFyZSBnaXZlbiAkUSQgcXVlcmllcywgd2hlcmUgZWFjaCBxdWVyeSBjb250YWlucyBhIHNldCAkUyQuIEZvciBlYWNoIHF1ZXJ5LCB5b3Ugc2hvdWxkIGNvbXB1dGUgdGhlIHF1YW50aXR5ICRcXG1hdGhpdHtzdHJlbmd0aH0oUykkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkTiQsIHRoZSBudW1iZXIgb2YgdmVydGljZXMgKCQyIFxcbGUgTiBcXGxlIDI1MFxcLDAwMCQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICROIC0gMSQgbGluZXMgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkYSQgYW5kICRiJDogdGhlIHZlcnRpY2VzIGNvbm5lY3RlZCBieSBhbiBlZGdlICgkMSBcXGxlIGEsIGIgXFxsZSBOJCkuIFRvZ2V0aGVyLCB0aGUgZWRnZXMgZm9ybSBhIHRyZWUuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkUSQsIHRoZSBudW1iZXIgb2YgcXVlcmllcyAoJDEgXFxsZSBRIFxcbGUgMTAwXFwsMDAwJCkuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgJFEkIGxpbmVzIGNvbnRhaW5zIGEgcXVlcnksIGRlbm90ZWQgYnkgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLiBBIHF1ZXJ5IHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgJEskLCB0aGUgc2l6ZSBvZiB0aGUgc2V0ICgkMSBcXGxlIEsgXFxsZSBOJCkuIEl0IGlzIGZvbGxvd2VkIGJ5ICRLJCBkaXN0aW5jdCBpbnRlZ2VycyBmcm9tICQxJCB0byAkTiQgaW4gYXJiaXRyYXJ5IG9yZGVyOiB0aGUgdmVydGljZXMgb2Ygc2V0ICRTJC48XC9wPlxyXG5cclxuPHA+VGhlIHN1bSBvZiAkSyQgaW4gZWFjaCB0ZXN0IGNhc2UgaXMgYXQgbW9zdCAkMVxcLDAwMFxcLDAwMCQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggb2YgdGhlICRRJCBxdWVyaWVzLCBwcmludCBhIHNpbmdsZSBsaW5lIHdpdGggdGhlIGludGVnZXIgJFxcbWF0aGl0e3N0cmVuZ3RofShTKSQgYXMgZGVmaW5lZCBhYm92ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic3VidGFzazEiOiI8cD4kTiA9IDMkLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gJmxlOyA1MCQsICRRICZsZTsgNTAkLjxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JE4gJmxlOyAyXFwsNTAwJCwgJFEgJmxlOyAyXFwsNTAwJC48XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1YWMwMSBcdWM5YzhcdWM3NThcdWM1ZDBcdWMxMWMsICRLID0gMyQuPFwvcD5cclxuIiwic3VidGFzazUiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGMuPFwvcD5cclxuIn1d

채점 및 기타 정보

• 예제는 채점하지 않는다.

첫 번째 줄에 정수 $N$이 주어진다.

다음 ($N - 1$)개의 줄에 각 간선에 대한 정보가 주어진다. 이 중 $i$ ($1 ≤ i ≤ N - 1$)번째 줄에는 두 정수 $A_i$, $B_i$가 주어진다.

다음 줄에 정수 $Q$가 주어진다.

다음 $Q$개의 줄에 각 질의에 대한 정보가 주어진다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄은 $i$번째 질의를 나타내며, 정수 $K$와 $K$개의 정수 $s_1, \dots , s_K$가 차례대로 주어진다.

첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다.