Очень легко потеряться в густых джунглях, и порой единственный способ найти выход — это блуждать. К счастью, в наших джунглях побывали очень опытные путешественники и проложили тропинки.

Есть всего $$$n$$$ деревьев и $$$n-1$$$ тропинок, каждая из которых соединяет два дерева. Дополнительно известно, что между любыми двумя деревьями существует ровно один путь по тропинкам, не проходящий по одной и той же тропинке дважды.

На протяжении последних нескольких дней в джунглях независимо оказывались $$$q$$$ людей без карты и других способов навигации. Вам известно по записям спасателей, что $$$i$$$-й из них начинал свой маршрут у дерева $$$s_i$$$ и блуждал до того, как в первый раз доходил до дерева $$$t_i$$$ где он находил записку от спасателей где был написан способ выхода из джунглей.

Каждый из этих людей блуждал абсолютно случайным образом, смотря на каждом шагу на всевозможные тропинки по которым он может пойти, и равновероятно выбирая любой из них, доходя до другого конца тропинки и заново повторяя этот процесс. Вероятность перемещения с дерева $$$u$$$ на соединенное тропинкой дерево $$$v$$$ была равна $$$\frac{1}{c_u}$$$, где $$$c_u$$$ — общее количество тропинок у дерева $$$u$$$. Каждый из них никогда не сдавался и никогда не оставался у того же самого дерева, постоянно ходя по тропинкам и ища выход.

Однако в записях не было указано, сколько времени блуждал каждый из этих потерянных людей. Чтобы оценить это число, вам нужно найти математическое ожидание числа шагов, необходимых для каждого человека, чтобы достичь дерева $$$t_i$$$ из дерева $$$s_i$$$.