def int(b = 0)
  read_line.to_i64 + b
end

def ints(b = 0)
  read_line.split.map { |x| x.to_i64 + b }
end

def str
  read_line.chomp
end

macro chmax(a, b)
 ({{a}} < {{b}} && ({{a}} = {{b}}))
end

macro chmin(a, b)
 ({{a}} > {{b}} && ({{a}} = {{b}}))
end

macro make_array(s, x)
  Array.new({{ s[0] }}) {
    {% if s[1..s.size].empty? %}; {{ x }}
    {% else %}; make_array({{ s[1..s.size] }}, {{ x }}) {% end %}
  }
end

OO = (1_i64 << 62) - (1_i64 << 31)
module NgLib
  # 不変な数列 $A$ に対して、$\sum_{i=l}^{r-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。
  class StaticRangeSum(T)
    getter size : Int64
    getter csum : Array(T)

    # 配列 `array` に対して累積和を構築します。
    #
    # ```
    # array = [1, 1, 2, 3, 5, 8, 13]
    # csum = StaticRangeSum(Int32).new(array)
    # ```
    def initialize(array : Array(T))
      @size = array.size.to_i64
      @csum = Array.new(@size + 1, T.zero)
      @size.times { |i| @csum[i + 1] = @csum[i] + array[i] }
    end

    # $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
    #
    # ```
    # array = [1, 1, 2, 3, 5, 8, 13]
    # csum = StaticRangeSum(Int32).new(array)
    # csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
    # ```
    def get(l, r) : T
      raise IndexError.new("`l` must be less than or equal to `r` (#{l}, #{r})") unless l <= r
      @csum[r] - @csum[l]
    end

    # :ditto:
    def get(range : Range(Int?, Int?)) : T
      l = (range.begin || 0)
      r = if range.end.nil?
            @size
          else
            range.end.not_nil! + (range.exclusive? ? 0 : 1)
          end
      get(l, r)
    end

    # $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
    #
    # $l \leq r$ を満たさないとき、`nil` を返します。
    #
    # ```
    # array = [1, 1, 2, 3, 5, 8, 13]
    # csum = StaticRangeSum(Int32).new(array)
    # csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
    # csum.get?(7...5) # => nil
    # ```
    def get?(l, r) : T?
      return nil unless l <= r
      get(l, r)
    end

    # :ditto:
    def get?(range : Range(Int?, Int?)) : T?
      l = (range.begin || 0)
      r = if range.end.nil?
            @size
          else
            range.end.not_nil! + (range.exclusive? ? 0 : 1)
          end
      get?(l, r)
    end

    # $\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。
    def get!(l, r) : T
      @csum[r] - @csum[l]
    end

    # :ditto:
    def get!(range : Range(Int?, Int?)) : T
      l = (range.begin || 0)
      r = if range.end.nil?
            @size
          else
            range.end.not_nil! + (range.exclusive? ? 0 : 1)
          end
      get!(l, r)
    end

    # `get(l : Int, r : Int)` へのエイリアスです。
    def [](l, r) : T
      get(l, r)
    end

    # `get(range : Range(Int?, Int?))` へのエイリアスです。
    def [](range : Range(Int?, Int?)) : T
      get(range)
    end

    # `get(l : Int, r : Int)` へのエイリアスです。
    def []?(l, r) : T?
      get?(l, r)
    end

    # `get?(range : Range(Int?, Int?))` へのエイリアスです。
    def []?(range : Range(Int?, Int?)) : T?
      get?(range)
    end
  end
end
module NgLib
  # 不変な数列 $A$ について、以下の条件を満たす演算を、区間クエリとして処理します。
  # - 結合則 : $(x \oplus y) \oplus z = x \oplus (y \oplus z)$
  # - 冪等性 : $x \oplus x = x$
  #
  # 前計算は $O(N \log{N})$ かかりますが、区間クエリには $O(1)$ で答えられます。
  class SparseTable(T)
    getter size : Int32
    @data : Array(T)
    @table : Array(Array(T))
    @lookup : Array(Int32)
    @op : (T, T) -> T

    # $\oplus = \max$ としてデータ構造を構築します。
    def self.max(elems : Enumerable(T))
      new elems, ->(x : T, y : T) { x > y ? x : y }
    end

    # $\oplus = \min$ としてデータ構造を構築します。
    def self.min(elems : Enumerable(T))
      new elems, ->(x : T, y : T) { x < y ? x : y }
    end

    # $\oplus = \mathrm{bitwise-or}$ としてデータ構造を構築します。
    def self.bitwise_or(elems : Enumerable(T))
      new elems, ->(x : T, y : T) { x | y }
    end

    # $\oplus = \mathrm{bitwise-and}$ としてデータ構造を構築します。
    def self.bitwise_and(elems : Enumerable(T))
      new elems, ->(x : T, y : T) { x & y }
    end

    # $\oplus = \mathrm{gcd}$ としてデータ構造を構築します。
    def self.gcd(elems : Enumerable(T))
      new elems, ->(x : T, y : T) { x.gcd(y) }
    end

    # $\oplus = op$ としてデータ構造を構築します。
    def initialize(elems : Enumerable(T), @op : (T, T) -> T)
      @size = elems.size
      @data = Array(T).new
      log = (0..).index! { |k| (1 << k) > @size }

      @table = Array.new(log) { Array(T).new(1 << log, T.zero) }
      elems.each_with_index { |e, i| @table[0][i] = e; @data << e }

      (1...log).each do |i|
        j = 0
        while j + (1 << i) <= (1 << log)
          @table[i][j] = @op.call(@table[i - 1][j], @table[i - 1][j + (1 << (i - 1))])
          j += 1
        end
      end

      @lookup = [0] * (@size + 1)
      (2..@size).each do |i|
        @lookup[i] = @lookup[i >> 1] + 1
      end
    end

    # `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。
    #
    # ```
    # rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
    # rmq.prod(0...3) # => 1
    # ```
    def prod(range : Range(Int?, Int?))
      l = (range.begin || 0)
      r = if range.end.nil?
            @size
          else
            range.end.not_nil! + (range.exclusive? ? 0 : 1)
          end

      b = @lookup[r - l]
      @op.call(@table[b][l], @table[b][r - (1 << b)])
    end

    # `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。
    #
    # $0 \leq l \leq r \leq n$ を満たさないとき、`nil` を返します。
    #
    # ```
    # rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
    # rmq.prod(0...3) # => 1
    # ```
    def prod?(range : Range(Int?, Int?))
      l = (range.begin || 0)
      r = if range.end.nil?
            @size
          else
            range.end.not_nil! + (range.exclusive? ? 0 : 1)
          end

      return nil unless 0 <= l && l <= r && r <= @size
      prod(range)
    end

    # $a_i$ を返します。
    def [](i)
      @data[i]
    end

    # $a_i$ を返します。
    #
    # 添字が範囲外のとき、`nil` を返します。
    def []?(i)
      @data[i]?
    end

    # `prod` へのエイリアスです。
    def [](range : Range(Int?, Int?))
      prod(range)
    end

    # `prod?` へのエイリアスです。
    def []?(range : Range(Int?, Int?))
      prod?(range)
    end
  end
end

class StronglyConnectedComponents
  alias Graph = Array(Array(Int64))

  getter leader : Array(Int64)
  getter graph : Graph
  getter groups : Array(Array(Int64))
  @n : Int64
  @order : Array(Int64)
  @fwd : Graph
  @bwd : Graph
  @closed : Array(Bool)

  def initialize(@fwd : Graph)
    @n = @fwd.size.to_i64
    @order = Array(Int64).new(@n)
    @leader = Array.new(@n, -1_i64)
    @bwd = Array.new(@n){ Array(Int64).new }
    @n.times do |i|
      @fwd[i].each do |j|
        @bwd[j] << i
      end
    end

    @closed = Array(Bool).new(@n, false)
    @n.times{ |i| dfs(i) }
    @order = @order.reverse
    ptr = rdfs

    @graph = Array.new(ptr){ Array(Int64).new }
    @groups = Array.new(ptr){ Array(Int64).new }
    @n.times do |i|
      @groups[@leader[i]] << i
      @fwd[i].each do |j|
        x, y = @leader[i], @leader[j]
        next if x == y
        @graph[x] << y
      end
    end
  end

  def same(u : Int, v : Int)
    leader[u] == leader[v]
  end

  def size
    @groups.size
  end

  def size(v : Int)
    @groups[leader[v]].size
  end

  private def dfs(i : Int)
    return if @closed[i]
    @closed[i] = true
    @fwd[i].each{ |j| dfs(j) }
    @order << i
  end

  private def rdfs
    ptr = 0_i64
    closed = Array.new(@n, false)
    @order.each do |s|
      next if closed[s]
      que = Deque(Int64).new
      que << s
      closed[s] = true
      @leader[s] = ptr
      until que.empty?
        now = que.shift
        @bwd[now].each do |nxt|
          next if closed[nxt]
          closed[nxt] = true
          @leader[nxt] = ptr
          que << nxt
        end
      end
      ptr += 1
    end
    ptr
  end
end

struct Int64
  def self.inf
    OO
  end
end

module NgLib
  struct Edge
    @data : {Int64, Int64}

    def initialize(t : Int64, w : Int64)
      @data = {t, w}
    end

    def self.to
      @data[0]
    end

    def self.weight
      @data[1]
    end

    def [](i : Int)
      @data[i]
    end
  end
end
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr
#
# Copyright 2023 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

module AtCoder
  # Implements standard priority queue like [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue).
  #
  # ```
  # q = AtCoder::PriorityQueue(Int64).new
  # q << 1_i64
  # q << 3_i64
  # q << 2_i64
  # q.pop # => 3
  # q.pop # => 2
  # q.pop # => 1
  # ```
  class PriorityQueue(T)
    include Enumerable(T)

    getter heap : Array(T)

    # Create a new queue in ascending order of priority.
    def self.max
      self.new { |a, b| a <= b }
    end

    # Create a new queue in ascending order of priority with the elements in *enumerable*.
    def self.max(enumerable : Enumerable(T))
      self.new(enumerable) { |a, b| a <= b }
    end

    # Create a new queue in descending order of priority.
    def self.min
      self.new { |a, b| a >= b }
    end

    # Create a new queue in descending order of priority with the elements in *enumerable*.
    def self.min(enumerable : Enumerable(T))
      self.new(enumerable) { |a, b| a >= b }
    end

    def initialize
      initialize { |a, b| a <= b }
    end

    # Initializes queue with the elements in *enumerable*.
    def self.new(enumerable : Enumerable(T))
      self.new(enumerable) { |a, b| a <= b }
    end

    # Initializes queue with the custom comperator.
    #
    # If the second argument `b` should be popped earlier than
    # the first argument `a`, return `true`. Else, return `false`.
    #
    # ```
    # q = AtCoder::PriorityQueue(Int64).new { |a, b| a >= b }
    # q << 1_i64
    # q << 3_i64
    # q << 2_i64
    # q.pop # => 1
    # q.pop # => 2
    # q.pop # => 3
    # ```
    def initialize(&block : T, T -> Bool)
      @heap = Array(T).new
      @compare_proc = block
    end

    # Initializes queue with the elements in *enumerable* and the custom comperator.
    #
    # If the second argument `b` should be popped earlier than
    # the first argument `a`, return `true`. Else, return `false`.
    #
    # ```
    # q = AtCoder::PriorityQueue.new([1, 3, 2]) { |a, b| a >= b }
    # q.pop # => 1
    # q.pop # => 2
    # q.pop # => 3
    # ```
    def initialize(enumerable : Enumerable(T), &block : T, T -> Bool)
      @heap = enumerable.to_a
      @compare_proc = block

      len = @heap.size
      (len // 2 - 1).downto(0) do |parent|
        v = @heap[parent]
        child = parent * 2 + 1
        while child < len
          if child + 1 < len && @compare_proc.call(@heap[child], @heap[child + 1])
            child += 1
          end
          unless @compare_proc.call(v, @heap[child])
            break
          end
          @heap[parent] = @heap[child]
          parent = child
          child = parent * 2 + 1
        end
        @heap[parent] = v
      end
    end

    # Pushes value into the queue.
    def push(v : T)
      @heap << v
      index = @heap.size - 1
      while index != 0
        parent = (index - 1) // 2
        if @compare_proc.call(@heap[index], @heap[parent])
          break
        end
        @heap[parent], @heap[index] = @heap[index], @heap[parent]
        index = parent
      end
    end

    # Alias of `push`
    def <<(v : T)
      push(v)
    end

    # Pops value from the queue.
    def pop
      if @heap.size == 0
        return nil
      end
      if @heap.size == 1
        return @heap.pop
      end
      ret = @heap.first
      @heap[0] = @heap.pop
      index = 0
      while index * 2 + 1 < @heap.size
        child = if index * 2 + 2 < @heap.size && !@compare_proc.call(@heap[index * 2 + 2], @heap[index * 2 + 1])
                  index * 2 + 2
                else
                  index * 2 + 1
                end
        if @compare_proc.call(@heap[child], @heap[index])
          break
        end
        @heap[child], @heap[index] = @heap[index], @heap[child]
        index = child
      end
      ret
    end

    # Yields each item in the queue in comparator's order.
    def each(&)
      @heap.sort { |a, b| @compare_proc.call(a, b) ? 1 : -1 }.each do |e|
        yield e
      end
    end

    # Returns, but does not remove, the head of the queue.
    def first(&)
      @heap.first { yield }
    end

    # Returns `true` if the queue is empty.
    delegate :empty?, to: @heap

    # Returns size of the queue.
    delegate :size, to: @heap
  end
end

module NgLib
  abstract struct Weight
    include Comparable(Weight)

    def self.zero : self
    end

    def self.inf : self
    end

    def +(other : self)
    end

    def <=>(other : self)
    end
  end

  class DijkstraGraph(Weight)
    record Edge(W), target : Int32, weight : W

    getter size : Int32
    @graph : Array(Array(Edge(Weight)))

    # $n$ 頂点 $0$ 辺からなるグラフを作成します。
    #
    # ```
    # graph = Dijkstra.new(n)
    # ```
    def initialize(n : Int)
      @size = n.to_i32
      @graph = Array.new(@size) { Array(Edge(Weight)).new }
    end

    # 非負整数の重み $w$ の辺 $(u, v)$ を追加します。
    #
    # `directed` が `true` の場合、
    # 有向辺とみなして、$u$ から $v$ への辺のみ生やします。
    #
    # ```
    # graph = Dijkstra.new(n)
    # graph.add_edge(u, v, w)                 # => (u) <---w---> (v)
    # graph.add_edge(u, v, w, directed: true) # => (u) ----w---> (v)
    # ```
    def add_edge(u : Int, v : Int, w : Weight, directed : Bool = false)
      @graph[u.to_i32] << Edge.new(v.to_i32, w)
      @graph[v.to_i32] << Edge.new(u.to_i32, w) unless directed
    end

    # 全点対間の最短経路長を返します。
    #
    # ```
    # dists = graph.shortest_path
    # dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]
    # ```
    def shortest_path : Array(Array(Weight))
      (0...@size).map { |s| shortest_path(s) }
    end

    # 始点 `start` から各頂点への最短経路長を返します。
    #
    # ```
    # dist = graph.shortest_path(2)
    # dist # => [3, 8, 0, 7, 1]
    # ```
    def shortest_path(start : Int) : Array(Weight)
      dist = [Weight.inf] * @size
      dist[start] = Weight.zero
      next_node = AtCoder::PriorityQueue({Weight, Int32}).min
      next_node << {Weight.zero, start.to_i32}

      until next_node.empty?
        d, source = next_node.pop.not_nil!
        next if dist[source] < d
        @graph[source].each do |e|
          next_cost = dist[source] + e.weight
          if next_cost < dist[e.target]
            dist[e.target] = next_cost
            next_node << {next_cost, e.target}
          end
        end
      end

      dist
    end

    # 始点 `start` から終点 `dest` への最短経路長を返します。
    #
    # ```
    # dist = graph.shortest_path(start: 2, dest: 0)
    # dist # => 12
    # ```
    def shortest_path(start : Int, dest : Int) : Weight
      shortest_path(start)[dest]
    end

    # 始点 `start` から終点 `dest` への最短経路の一例を返します。
    #
    # ```
    # route = graph.shortest_path_route(start: 2, dest: 0)
    # route # => [2, 7, 1, 0]
    # ```
    def shortest_path_route(start, dest)
      prev = impl_memo_route(start)

      res = Array(Int32).new
      now : Int32? = dest.to_i32
      until now.nil?
        res << now.not_nil!
        now = prev[now]
      end

      res.reverse
    end

    # 始点 `start` から最短路木を構築します。
    #
    # 最短路木は `start` からの最短経路のみを残した全域木です。
    #
    # ```
    # route = graph.shortest_path_route(start: 2, dest: 0)
    # route # => [2, 7, 1, 0]
    # ```
    def shortest_path_tree(start, directed : Bool = false) : Array(Array(Int32))
      dist = [Weight.inf] * @size
      dist[start] = Weight.zero
      next_node = AtCoder::PriorityQueue({Weight, Int32}).min
      next_node << {Weight.zero, start.to_i32}

      birth = [-1] * @size
      until next_node.empty?
        d, source = next_node.pop.not_nil!
        next if dist[source] < d
        @graph[source].each do |e|
          next_cost = dist[source] + e.weight
          if next_cost < dist[e.target]
            dist[e.target] = next_cost
            next_node << {next_cost, e.target}
            birth[e.target] = source
          end
        end
      end

      tree = Array.new(@size) { [] of Int32 }
      @size.times do |target|
        source = birth[target]
        next if source == -1
        tree[source] << target
        tree[target] << source unless directed
      end

      tree
    end

    # 経路復元のための「どこから移動してきたか」を
    # メモした配列を返します。
    private def impl_memo_route(start)
      dist = [Weight.inf] * @size
      dist[start] = Weight.zero
      prev = Array(Int32?).new(@size) { nil }
      next_node = AtCoder::PriorityQueue({Weight, Int32}).min
      next_node << {Weight.zero, start.to_i32}

      until next_node.empty?
        d, source = next_node.pop.not_nil!
        next if dist[source] < d
        @graph[source].each do |e|
          next_cost = dist[source] + e.weight
          if next_cost < dist[e.target]
            dist[e.target] = next_cost
            prev[e.target] = source
            next_node << {next_cost, e.target}
          end
        end
      end

      prev
    end
  end
end

class Array(T)
  def compress
    b = clone.sort.uniq
    map{ |s| b.bsearch_index{ |x| x >= s } || b.size }
  end

  def mapping
    b = clone.sort.uniq
    f, g = Hash(Int64, Int64).new, Hash(Int64, Int64).new
    each do |s|
      index = b.bsearch_index{ |x| x >= s } || b.size
      f[s] = index
      g[index] = s
    end
    {f, g}
  end
end

#                                           .O,                                        
#                                          :o.                                         
#                                        'd'          :c;.                            c
#                                       lc  dKl     ;d,.,cl:.           oOx.           
#                                     .x.   .,.   'd:.......:ll;.       'lc            
#                                   .;0;        .ol............'col;.                  
#                                .:do;xl       cd'.................,col;.              
#                           .,cdd:'   od     'x;........:..............':ol;.          
#                     ..;lddc,.       od    od....l:...;x.........,........,lo;        
#              .,:loodl;.          .,,kx. .kk:....k,...lo........od.........;.:x,      
#       .,coool:,.                  ....;lkodl....O:...dk.......;Oo........:x...oo     
#    :dl;'.                                .lk:...Ok...xkc......xcx.......,k'....:x    
#  ;k,                                        :x:.Olx'.O'd;....;o.O......;Oc......cx   
#  O,                       .                   ;xO;.cOO..ll,..l: x,...,dck,.......dc  
#  k:                      lKd                    oO. KK   .;cld; dc;lOc.;d........,0  
#  dl                       .                      cx.cO.         .,.KW..x'.........0. 
#  oc         .ll;.                                 :k.l:            ;l,k,...;:.....0. 
#  o,         kkxkOOOOOOOOOkkkkxl:'.                 ;x.,.           .dOoccod:.....cO  
#  x..o.     lOxxxxxxxxxxxxxxxxxxkXOOdc'              oc    .l;,,,;coo:...ol......o0,  
#  O  '     xOxxxxxxxxxxxxxxxxxxxxKOxxkOOd;           .0.   '0:ccc:,,,0ccd;....;lx0l   
# .x      .Okxxxxxxxxxxxxxxxxxxxxx0KxxxxxxkOo.         O'    do'''''''OllOkoooolckl    
# ;l     .OkxxxxxxxxxxxxxxxxxxxxxxOKxxxxxkOxk0l        kkollll0kdoddxkK0Oxllooool.     
# c:     kKxxxxxxxxxxxxxxxxxxxxxxx0XkxxxxkXxxxOO       k'  ;d. .k,....':ok0dc;..   .'::
# o,    xO00xxxxxxxxxxxxxxxxxxxxxxKOKxxxxxXdoOk0;     .O  ;d  .k.         .cd,ckccc;lx,
# d,   c0xx0Kkxxxxxxxxxxxxxxxxxxx0O.KkxxxkX. .0K;     lk:lOo;;Oo;kd;     ' .x;:c      .
# d,  .0KxxxkK0kxxxxxxxxxxxxxxxx0k. l0xxxOx   O0     'O::k; .kckO: Okollxxkx. k.       
# d,  xod0xxxxK00OxxxxxxxxxxxxO0l.  'XxxkK'  ;K,    .Oxxo.  .o x: ;O;;xo..K. l:        
# l;  0:;d0xxxkO.;ok0OkO00OkO0l.     KkkKc';d0,   ;olxx     ,dd; 'Kkkk, 'Oc 'x         
# :l  K:;;o0kxxKc   .':c..:o,.       O0OlO0Kd. 'ol. :d      lO' ;00x;. ck'  O.         
# 'x  0c;;;cO0xkXk,               '. cdk00x..cOx   ol     .od.  ,c.  'k;   d;          
#  0. kl;;;;;oO0OK0,              ,ccO00KOokk.'x. o:   'cx0; .::c:. od    ;d           
#  ;d..xd:;;;;;cdkkk,...    ..';llc::,...   ;d..xkc  .klld.      ol ol   .k            
#    ,llokkolcccloddkK0K00ck00xodoo:.         cl '   .o..d:      c. ,k   k.            
#       .,:c::;,..  ;d  .0;k. ;lodxkKo         .d'        :x;'.....:xc  lc             
#                   lx :OOOol       'O           :o.        dOooodd0.  .O              
#                  lxc:,k:O .d;     ll            .dc        ld;;;;O'  l;              
#               .c, dk:k;.k   oOcc,,O.              ,x.       Oc;;;x:  x.              
#             .ld.'lkd;,:cdlc;;0, .:'                 dxcc:;,'kdllld0;',..    ;loodoool
#           ,ol.     .oo.    ...' .:::cccl:.           :x. .............';codOc;;;;;;;;
#        :kd,          co                 .'c,          'k.                  ,dx:;;;;;;
#         .:llld;,;:....O'                               .x:                  .ko;;;;;;
#               'lkcodxdxO.                                ;x,                :kc;;;;;;
#                ;k;;;;;;dx                                  o0'               ;Kd;;;;;

n = int
skills = (1..n - 1).map { ints }
q = int
queries = (1..q).map { ints }

graph = Array.new(n) { [] of NgLib::Edge }
scc_graph = Array.new(n) { [] of Int64 }
skills.each_with_index do |(l, a), i|
  graph[a - 1] << NgLib::Edge.new(i + 1, l)
  scc_graph[a - 1] << i + 1
end

scc = StronglyConnectedComponents.new(scc_graph)

# 技 i を覚えるのに必要な最小コスト
dist = [-OO] * n
dist[0] = 0
queue = Deque({Int64, Int64}).new
queue << {0_i64, -1_i64}
until queue.empty?
  from, par = queue.pop
  graph[from].each do |(to, w)|
    next if to == par
    chmax(dist[to], Math.max(dist[from], w))
    queue << {to, from}
  end
end

n.times do |i|
  dist[i] = OO if dist[i] == -OO
  dist[i] = OO if scc.size(i) >= 2
end

# 技 i を覚えるための最小コスト
rmq = NgLib::SparseTable(Int64).max(dist)

# レベル x 以下の技は何個？
lvs = [] of Int64
queries.each do |(t, x)|
  lvs << x if t == 1
end
f, g = (dist + lvs).mapping
cnt = [0_i64] * f.size
dist.each_with_index do |lv, i|
  cnt[f[lv]] += 1
end
csum = NgLib::StaticRangeSum(Int64).new(cnt)

queries.each do |(t, x)|
  y = x
  case t
  when 1
    ans = csum[0..f[x]]
    puts ans
  when 2
    ans = dist[y - 1]
    puts ans >= OO ? -1 : ans
  end
end