output_description: If there exists an integer i satisfying the following condition, print the
  minimum such i; otherwise, print `-1`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      s
      t
attempt: import sys
  
  sys.setrecursionlimit(100000000)
  
  
  class Graph:
  
      def __init__(self, N):
          self.V = {}
          self.E = {}
  
          for i in range(N):
              self.V[i + 1] = 0
              self.E[i + 1] = {}
  
      def add_edge(self, u, v, w):
          self.E[u][v] = w
  
  
  def calc(N, G):
      result = [0] * N
  
      def walk(u, current_value=0):
          current_value = G.V[u] + current_value
          result[u - 1] = current_value
          for v in G.E[u]:
              walk(v, current_value)
  
      walk(1, 0)
  
      return result
  
  
  N, Q = map(int, input().strip().split())
  
  G = Graph(N)
  
  for _ in range(N - 1):
      a, b = map(int, input().strip().split())
      G.add_edge(a, b, 0)
  
  for _ in range(Q):
      p, x = map(int, input().strip().split())
      G.V[p] += x
  
  result = calc(N, G)
  
  print(" ".join(map(str, result)))
  
problem_description: Statement
  
  Given are two strings s and t consisting of lowercase English letters.
  Determine if there exists an integer i satisfying the following condition, and
  find the minimum such i if it exists.
  
    * Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').
samples: [{"input": "contest\n    son", "output": "10\n    \n\nt = `son` is a subsequence of the string `contestcon` (the first 10 characters\nin s' = `contestcontestcontest...`), so i = 10 satisfies the condition.\n\nOn the other hand, t is not a subsequence of the string `contestco` (the first\n9 characters in s'), so i = 9 does not satisfy the condition.\n\nSimilarly, any integer less than 9 does not satisfy the condition, either.\nThus, the minimum integer i satisfying the condition is 10.\n\n* * *"}, {"input": "contest\n    programming", "output": "-1\n    \n\nt = `programming` is not a substring of s' = `contestcontestcontest...`. Thus,\nthere is no integer i satisfying the condition.\n\n* * *"}, {"input": "contest\n    sentence", "output": "33\n    \n\nNote that the answer may not fit into a 32-bit integer type, though we cannot\nput such a case here."}]