В Байтландии есть \(n\) городов, некоторые пары которых соединены дорогами, по которым можно ездить в обе стороны. \(i\)-я дорога характеризуется сложностью проезда по ней \(w_i\). Время проезда по дороге со сложностью \(w_i\) равняется \(\lceil\frac{w_i}{c}\rceil\) часов, где \(c\) — навык вождения водителя.
Транспортная система Байтландии представляет собой дерево. Иными словами, между любой парой городов существует ровно один путь, который проходит по каждому городу не более одного раза.
В некоторых городах можно посетить курсы вождения. Если провести в таком городе, изучая курсы, \(T\) часов, то навык вождения \(c\) увеличивается в \(2\) раза. Заметьте, что значение \(T\) одинаково во всех городах, и курсы можно посещать в одном и том же городе несколько раз.
Вам нужно ответить на \(q\) запросов: за какое минимальное время можно добраться из города \(a\) в город \(b\), если начать путь с навыком вождения \(c = 1\)?
Выходные данные
Для каждого запроса выведите одно целое число в отдельной строке — минимальное время, за которое можно добраться в соответствующем запросе.
Примечание
В первом наборе входных данных в первом запросе оптимально не проходить курсы вождения. Тогда минимальное время равно сложности дороги между городами \(1\) и \(2\), которое равно \(1\).
Во втором наборе входных данных в первом запросе оптимально вначале пройти курсы вождения за \(3\) часа в городе \(1\) один раз, а потом поехать в город \(5\). Тогда всего путь займёт \(3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11\) часов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 3
1 2 1
11
1
1 2
5 3
1 4 5
1 3 8
2 3 8
4 5 10
11001
5
1 5
2 5
5 1
3 4
4 2
|
1
11
14
11
13
15
|