В этой задаче вам требуется помочь Берляндской армии организовать их систему распространения приказов.
Всего в Берляндской армии есть \(n\) офицеров. Первый офицер — командующий армии, он не имеет никаких вышестоящих командующих. Любой другой офицер имеет ровно одного непосредственного командующего. Если офицер \(a\) является непосредственным командующим офицера \(b\), то можно сказать, что офицер \(b\) непосредственный подчиненный офицера \(a\).
Офицер \(x\) является подчиненным (непосредственным или по цепочке) офицера \(y\), если выполняется одно из следующих условий:
- офицер \(y\) непосредственный командующий офицера \(x\);
- непосредственный командующий офицера \(x\) является подчиненным офицера \(y\).
Например, на картинке ниже подчиненными офицера \(3\) являются: \(5, 6, 7, 8, 9\).
Структура Берляндской армии организована таким образом, что каждый офицер, кроме командующего, является подчиненным командующего армией.
Формально, Берляндская армия может быть представлена как дерево, состоящее из \(n\) вершин, в котором вершина \(u\) соответствует офицеру с номером \(u\). Предок вершины \(u\) соответствует непосредственному командующему офицера \(u\). Корень (который имеет номер \(1\)) соответствует командующему армией.
Военное министерство Берляндии приказало вам ответить на \(q\) запросов, \(i\)-й запрос представлен в виде \((u_i, k_i)\), где \(u_i\) — это некоторый офицер, а \(k_i\) — некоторое натуральное число.
Для обработки \(i\)-го запроса представим, как приказ, отданный офицером с номером \(u_i\) распространяется по поддереву \(u_i\). Этот алгоритм очень похож на DFS (depth first search, обход в глубину).
Представим, что сейчас распространяет приказ офицер с номером \(a\). Офицер \(a\) выбирает \(b\) — одного из своих непосредственных подчиненных (то есть сына в дереве), который еще не получил приказ. Если существует несколько таких непосредственных подчиненных, тогда \(a\) выбирает офицера с минимальным индексом среди них. Офицер \(a\) отдает приказ офицеру \(b\). После этого \(b\) использует такой же самый алгоритм, чтобы распространить приказ в своем поддереве. После того, как \(b\) прекращает распространять приказ, офицер \(a\) выбирает следующего непосредственного подчиненного (при помощи такого же алгоритма). Когда \(a\) не может выбрать непосредственного подчиненного, еще не получившего приказ, офицер \(a\) прекращает распространять приказ.
Посмотрим на следующий пример:
Если офицер \(1\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке : \([1, 2, 3, 5 ,6, 8, 7, 9, 4]\).
Если офицер \(3\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([3, 5, 6, 8, 7, 9]\).
Если офицер \(7\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([7, 9]\).
Если офицер \(9\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([9]\).
Чтобы ответить на \(i\)-й запрос \((u_i, k_i)\), сформируем последовательность того, в каком порядке офицеры будут получать приказ, если \(u_i\)-й офицер начал его распространять. Ответом будет являться \(k_i\)-й элемент сформированной последовательности или -1, если в ней меньше \(k_i\) элементов.
Запросы необходимо рассматривать независимо. Запрос не затрагивает следующие запросы.