У Фермера Джона есть \(N\) (\(2\le N\le 10^5\)) коров, помеченных \(1\dots N\),
где соединения между коровами описываются деревом. К несчастью, начала распространяться болезнь.
Изначально, инфицированы несколько коров. Каждую ночь инфицированная корова
передаёт болезнь своим соседям. Однажды инфицированная корова остаётся инфицированной.
После некоторого количества ночей ФД протестировал своих коров на наличие болезни.
И про каждую узнал больна она или нет.
Вам даны \(Q\) (\(1\le Q\le 20\)) различных значений количества ночей - каждое -
целое число в интервале \([0,N]\). Для каждого количества ночей определите минимальное
количество коров, которые были изначально инфицированы или укажите, что количество ночей
не соответствует информации об инфицированных коровах.
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\).
Следующая строка содержит битовую строку длины \(N\), где \(i\)-ый символ равен 1,
если \(i\)-ая корова инфицирована, иначе 0. По крайней мере одна корова инфицирована.
Следующие \(N-1\) строк описывают ребра дерева.
Затем \(Q\), за которым следуют \(Q\) значений количества ночей.
ФОРМАТ ВЫВОДА (на экран):
\(Q\) строк - ответы для каждого количества ночей или -1, если ответить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0
|
1
1
1
1
2
5
|