output_description: For each data set, if it includes sufficient information to classify all the
  inhabitants, print the identification numbers of all the divine ones in
  ascending order, one in a line. In addition, following the output numbers,
  print "end" in a line. Otherwise, i.e., if a given data set does not include
  sufficient information to identify all the divine members, print "no" in a
  line.
input_description: The input consists of multiple data sets, each in the following format:
  
      
      
      _n_ _p_ 1 _p_ 2
      _x_ 1 _y_ 1 _a_ 1
      _x_ 2 _y_ 2 _a_ 2
      ...
      _x_ _i_ _y_ _i_ _a_ _i_
      ...
      _x_ _n_ _y_ _n_ _a_ _n_
      
  
  The first line has three non-negative integers _n_ , _p_ 1, and _p_ 2. _n_ is
  the number of questions Akira asked. _p_ 1 and _p_ 2 are the populations of
  the divine and devilish tribes, respectively, in the legend. Each of the
  following _n_ lines has two integers _x i_, _y i_ and one word _a i_. _x i_
  and _y i_ are the identification numbers of inhabitants, each of which is
  between 1 and _p_ 1 \+ _p_ 2, inclusive. _a i_ is either "yes", if the
  inhabitant _x i_ said that the inhabitant _y i_ was a member of the divine
  tribe, or "no", otherwise. Note that _x i_ and _y i_ can be the same number
  since "are you a member of the divine tribe?" is a valid question. Note also
  that two lines may have the same _x_ 's and _y_ 's since Akira was very upset
  and might have asked the same question to the same one more than once.
  
  You may assume that _n_ is less than 1000 and that _p_ 1 and _p_ 2 are less
  than 300. A line with three zeros, i.e., "0 0 0", represents the end of the
  input. You can assume that each data set is consistent and no contradictory
  answers are included.
attempt: from collections import defaultdict
  
  
  class UnionFind:
      def __init__(self, n):
          self.parent = list(range(n))
          self.rank = [0] * n
  
      def find(self, x):
          if self.parent[x] == x:
              return x
          else:
              self.parent[x] = self.find(self.parent[x])
              return self.parent[x]
  
      def unite(self, x, y):
          x, y = self.find(x), self.find(y)
  
          if x == y:
              return
  
          if self.rank[x] < self.rank[y]:
              self.parent[x] = y
          else:
              self.parent[y] = x
              if self.rank[x] == self.rank[y]:
                  self.rank[x] += 1
  
  
  while True:
      n, p1, p2 = (int(s) for s in input().split())
      if not n:
          break
  
      p = p1 + p2
      tree = UnionFind(p * 2)
      unions = defaultdict(list)
  
      for i in range(n):
          xs, ys, a = input().split()
          x, y = int(xs) - 1, int(ys) - 1
          if a == "yes":
              tree.unite(x, y)
              tree.unite(x + p, y + p)
          else:
              tree.unite(x, y + p)
              tree.unite(x + p, y)
  
      for i in range(p):
          unions[tree.find(i)].append(i)
      roots = []
      sides = []
      diffs = []
      rest = p1
      for i in range(p):
          if i in unions:
              member_len, backside_len = len(unions[i]), len(unions[i + p])
              if member_len == backside_len:
                  rest = -1
                  break
              elif member_len < backside_len:
                  diff = backside_len - member_len
                  rest -= member_len
                  sides.append(0)
              else:
                  diff = member_len - backside_len
                  sides.append(1)
                  rest -= backside_len
              roots.append(i)
              diffs.append(diff)
      if rest < 0:
          print("no")
          continue
  
      dp = [[1] + [0] * rest for i in range(len(roots) + 1)]
  
      for i in reversed(range(len(roots))):
          for j in range(1, rest + 1):
              if j < diffs[i]:
                  if dp[i + 1][j]:
                      dp[i][j] = 1
                  else:
                      dp[i][j] = 0
              else:
                  if dp[i + 1][j] and dp[i + 1][j - diffs[i]]:
                      dp[i][j] = 3
                  elif dp[i + 1][j - diffs[i]]:
                      dp[i][j] = 2
                  elif dp[i + 1][j]:
                      dp[i][j] = 1
                  else:
                      dp[i][j] = 0
  
      divines = []
      for i in range(len(roots)):
          if dp[i][rest] == 1:
              divines.extend(unions[roots[i] + p * sides[i]])
          elif dp[i][rest] == 2:
              divines.extend(unions[roots[i] + p * (1 - sides[i])])
              rest -= diffs[i]
          else:
              print("no")
              break
      else:
          divines.sort()
          for divine in divines:
              print(divine + 1)
          print("end")
  
problem_description: G: True Liars
  
  After having drifted about in a small boat for a couple of days, Akira Crusoe
  Maeda was finally cast ashore on a foggy island. Though he was exhausted and
  despaired, he was still fortunate to remember a legend of the foggy island,
  which he had heard from patriarchs in his childhood. This must be the island
  in the legend.
  
  In the legend, two tribes have inhabited the island, one is divine and the
  other is devilish; once members of the divine tribe bless you, your future is
  bright and promising, and your soul will eventually go to Heaven; in contrast,
  once members of the devilish tribe curse you, your future is bleak and
  hopeless, and your soul will eventually fall down to Hell.
  
  In order to prevent the worst-case scenario, Akira should distinguish the
  devilish from the divine. But how? They looked exactly alike and he could not
  distinguish one from the other solely by their appearances. He still had his
  last hope, however. The members of the divine tribe are truth-tellers, that
  is, they always tell the truth and those of the devilish tribe are liars, that
  is, they always tell a lie.
  
  He asked some of the whether or not some are divine. They knew one another
  very much and always responded to him "faithfully" according to their
  individual natures (i.e., they always tell the truth or always a lie). He did
  not dare to ask any other forms of questions, since the legend says that a
  devilish member would curse a person forever when he did not like the
  question. He had another piece of useful information: the legend tells the
  populations of both tribes. These numbers in the legend are trustworthy since
  everyone living on this island is immortal and none have ever been born at
  least these millennia.
  
  You are a good computer programmer and so requested to help Akira by writing a
  program that classifies the inhabitants according to their answers to his
  inquiries.
samples: [{"input": "1 1\n    1 2 no\n    2 1 no\n    3 2 1\n    1 1 yes\n    2 2 yes\n    3 3 yes\n    2 2 1\n    1 2 yes\n    2 3 no\n    5 4 3\n    1 2 yes\n    1 3 no\n    4 5 yes\n    5 6 yes\n    6 7 no\n    0 0 0", "output": "no\n    no\n    1\n    2\n    end\n    3\n    4\n    5\n    6\n    end"}]