Савез Чаробњачких Банкара (СЧБ) има мрежу банака повезаних порталима, тачније минималним бројем портала потребних да се од сваке банке може доћи у сваку другу банку (портали су скупи за одржавање, па граф банака представља стабло), у којима чувају златнике. Помоћу ових портала могу слати златнике из једне банке до друге, порталом који их повезује, али за једно пребацивање једног златника кроз један портал, потребан им је један кристал тимпестина, ретког минерала, који се користи као гориво за овај процес. Савез жели у сваком тренутку да буде спреман за непредвиђене околности, и то на следећи начин: план је да се у случају узбуне сви златници пребаце у једну банку, како би се сви чаробњаци ујединили у њиховој заштити. При томе желимо да ово урадимо тако да потрошимо најмање кристала тимпестина, са обзиром да је он јако драгоцен. Како су ови банкари чаробњаци, а не програмери, и како људи стално долазе и стављају новац у банку, они не умеју довољно брзо да израчунају у коју банку би требало пребацити све златнике у случају узбуне. Помозите им и одредите у коју банку је најбоље пребацити све ресурсе у било ком тренутку!

Опис улаза

У првом реду стандардног улаза налази број \(N\), број банака. У наредних \(N-1\) редова се налазе по два цела броја \(x_i\) и \(y_i\), у опсегу од \(1\) до \(N\), који представљају повезаност банке \(x_i\) и \(y_i\) порталом. У следећем реду налази се \(N\) бројева, почетни број златника у свакој банци. У наредном реду се налази \(Q\), број упита. У следећих \(Q\) редова налазе се по два броја \(z_i\) и \(b_i\), који представљају долазак особе која ставља \(z_i\) златника у банку \(b_i\).

Опис излаза

Исписати \(Q+1\) бројева. Први број је оптимална банка у коју треба пребацити све златнике ако дође до узбуне пре доласка првог човека који прилаже новац, док су наредних \(Q\) бројева индекси оптималних банака након долазака сваког од залагача редом, то јест након сваког од упита. Ако има више оптималних банака, исписати ону са најмањим индексом.

Пример 1

Улаз

5
1 2
2 3
3 4
4 5
1 1 1 1 1
2
8 5
6 2

Излаз

3
5
4

Објашњење

• Пре доласка првог човека банка \(3\) је оптимална и требало би нам \(6\) кристала да све златнике пребацимо у њу.
• Након доласка првог човека банка \(5\) постаје оптимална, и требало би нам \(10\) кристала да све златнике пребацимо у њу.
• Након доласка другог човека банка \(4\) постаје оптимална, и треба нам \(15\) кристала ако желимо да пребацимо све златнике у њу.

Пример 2

Улаз

4
1 2
1 3
1 4
1 1 1 100
0

Излаз

4

Објашњење

• Пошто у последњој банци има убедљиво највише златника, јасно је да је неисплативо да их премештамо из ње.

Ограничења

• \(1 \leq N,Q \leq200.000\), почетни број златника у свакој банци је бар 1.

Тест примери су подељени у пет дисјунктних група:

• У тестовима вредним 15 поена: \(N \leq 1000, Q=0\).
• У тестовима вредним 15 поена: \(Q=0\).
• У тестовима вредним 20 поена: Свака банка је повезана са највише две друге банке.
• У тестовима вредним 20 поена: Граф банака представља комплетно бинарно стабло.
• У тестовима вредним 30 поена: Без додатних ограничења.