We need a system that can learn facts about family relationships, check their consistency and answer queries about them.

# The task

~~~if:javascript
Create a class `Family` with the following methods. All arguments are strings: names of persons. Upon the first use of a name, that name is added to the family.

* `male(name)` and `female(name)` returning `boolean`

 Define the gender (corresponding to the method name) of the given person. Return `false` when these assignments cannot be made because of conflicts with earlier registered information.
  
* `isMale(name)` and `isFemale(name)` returning `boolean`

 Return `true` when the person has the said gender. When no gender was assigned, both methods should return `false`
 
* `setParent(childName, parentName)` returning `boolean`

 Defines the child-parent relationship between two persons. Returns `false` when the relationship cannot be made because of conflicts with earlier registered information.

* `getParents(name)` and `getChildren(name)` returning `array` of `string`
 
 Return the names of the person's parents/children in alphabetical order
~~~
~~~if:python
Create a class `Family` with the following methods. All arguments are strings: names of persons. Upon the first use of a name, that name is added to the family.

* `male(name)` and `female(name)` returning `boolean`

 Define the gender (corresponding to the method name) of the given person. Return `False` when these assignments cannot be made because of conflicts with earlier registered information.
  
* `is_male(name)` and `is_female(name)` returning `boolean`

 Return `True` when the person has the said gender. When no gender was assigned, both methods should return `False`
 
* `set_parent_of(child_name, parent_name)` returning `boolean`

 Defines the child-parent relationship between two persons. Returns `False` when the relationship cannot be made because of conflicts with earlier registered information.

* `get_parents_of(name)` and `get_children_of(name)` returning `list` of `string`
 
 Return the names of the person's parents/children in alphabetical order
~~~
~~~if:java
Create a class `Family` with the following methods. All arguments are names of persons. Upon the first use of a name, that name is added to the family.

* `boolean male(String name)` and `boolean female(String name)`

 Define the gender (corresponding to the method name) of the given person. Return `false` when these assignments cannot be made because of conflicts with earlier registered information.
  
* `boolean isMale(String name)` and `boolean isFemale(String name)`

 Return `true` when the person has the said gender. When no gender was assigned, both methods should return `false`
 
* `boolean setParent(String childName, String parentName)`

 Defines the child-parent relationship between two persons. Returns `false` when the relationship cannot be made because of conflicts with earlier registered information.

* `List getParents(String name)` and `List getChildren(String name)`
 
 Return the names of the person's parents/children in alphabetical order
~~~
~~~if:php
Create a class `Family` with the following methods. All arguments are names of persons. Upon the first use of a name, that name is added to the family.

* `male(string $name): bool` and `female(string $name): bool`

 Define the gender (corresponding to the method name) of the given person. Return `false` when these assignments cannot be made because of conflicts with earlier registered information.
  
* `isMale(string $name): bool` and `isFemale(string $name): bool`

 Return `true` when the person has the said gender. When no gender was assigned, both methods should return `false`
 
* `setParent(string $child_name, string $parent_name): bool`

 Defines the child-parent relationship between two persons. Returns `false` when the relationship cannot be made because of conflicts with earlier registered information.

* `getParents(string $name): array` and `getChildren(string $name): array`
 
 Return the names of the person's parents/children in alphabetical order
~~~

# Deducing information

When things can be implied from given information, it should be done.

For instance, a parent's gender can be determined as soon as the other parent's gender becomes known:

```python
fam = Family()
fam.set_parent_of("Vera", "George")
fam.set_parent_of("Vera", "Vanessa")
fam.female("Vanessa")
fam.female("George");  # False, because:
fam.is_male("George"); # ...this is True.
```

~~~if:javascript,java,php
Also `setParentOf` can return `false`. For example, if the relationship would infer that one becomes their own ancestor:
~~~
~~~if:python
Also `set_parent_of` can return `False`. For example, if the relationship would infer that one becomes their own ancestor:
~~~

```python
fam = Family()
fam.set_parent_of("Vera", "George")
fam.set_parent_of("George", "Vera") # False
```

# Details, rules, assumptions

Although the task relates to genealogy, the rules of this kata are not claimed to be realistic. Several simplifications and rules apply, which may not hold in real life: 

- Strings are case sensitive, but there are no tests playing around with "Peter", "PETER" and "PeTeR".
- People are uniquely identified by their name. For instance, there are no two different people called "Jim" in the same family.
- Once a person has an assigned gender, it cannot be changed.
- No gender conclusions should be made from personal names: "Bob" could well be a woman and "Susan" a man.
- People cannot have more than one mother and one father.
- The terms "parents" and "children" refer to the relatives in the immediate previous/next generations only, not to more remote ancestors or descendants.
- Incest may occur, so, for example, one's parent may at the same time be their grandparent.
- One cannot be their own ancestor.
- Age is not accounted for. Even if some incestuous relationships would infer that one's parent is more than 5 generations older, it should be allowed.
- In case a name's first occurrence is in a call of one of the two gender querying methods, the return value will always be false, as that new person does not have a known gender.
- In case a name's first occurrence is in a call of one of the two relation querying methods, the return value will always be an empty array/list, as there are no relationships known yet in which that new person participates.
- For the reasons in the preceding two bullet points it should not matter whether you actually store that name in these cases in your data structure, or not. In the latter case you would only store it at the next occasion when that name is mentioned in a call of one of the three other methods, that actually *add* information. The described interface has no way to query the difference between these two possible implementations, so you can choose freely.

# Example

Consider the following family graph:


  .dot { height: 49px; width: 100px; background-color: #666; border-radius: 50%;
      border: #aaa 1px solid ; display: flex; align-items: center; justify-content: center; }
  table.tight { border-spacing: 0px; border-collapse: separate; width: 250px}
  table.tight td { padding: 0px; min-width: 25px; height: 25px; }
  .up { border-top: #aaa 1px solid; }
  .right { border-right: #aaa 1px solid; }
  .red { color: #ea6 }



Dylan (m)

Morgan (f)
















Frank (m)

July

Jennifer












Joy




It could be created step by step with the following code — the expected return value for each method call is indicated in comments:

```python
fam = Family()
fam.set_parent_of("Frank", "Morgan")       # True
fam.set_parent_of("Frank", "Dylan")        # True
fam.male("Dylan")                          # True
fam.male("Dylan")                          # True, no conflict
fam.set_parent_of("Joy", "Frank")          # True
fam.male("Frank")                          # True
fam.male("Morgan")                         # False
# (Morgan is a woman because she both is Frank's parent, but not his father) 
fam.set_parent_of("July", "Morgan")        # True
# (The preceding assertion was rejected, so there is no conflict)
fam.is_male("Joy") or fam.is_female("Joy") # False
# (We know Joy is Frank's child, but we can't derive Joy's gender)
fam.get_children_of("Morgan")              # ["Frank", "July"]
fam.set_parent_of("Jennifer", "Morgan")    # True
fam.get_children_of("Morgan")              # ["Frank", "Jennifer", "July"]
fam.get_children_of("Dylan")               # ["Frank"]
# (That is all we know for sure)
fam.get_parents_of("Frank")                # ["Dylan", "Morgan"]
fam.set_parent_of("Morgan", "Frank")       # False
# (It is impossible to be the parent of your parent)
```

Have fun!

Source: codewars | Difficulty: MEDIUM
Tags: Graph algorithms

Starter code: def __init__(self):
	

Solutions:
class family:

	def __init__(self):
		self.names = {}

	def male(self, n):
		return self.setsex(n, 'm')

	def female(self, n):
		return self.setsex(n, 'f')

	def is_male(self, n):
		return self.names[n]['sex'] == 'm' if n in self.names else False

	def is_female(self, n):
		return self.names[n]['sex'] == 'f' if n in self.names else False

	def get_parents_of(self, n):
		return sorted(self.names[n]['childof']) if n in self.names else []

	def get_children_of(self, n):
		return sorted(self.names[n]['parentof']) if n in self.names else []

	def updatesex(self):
		for n in [n for n in self.names if len(self.names[n]['childof']) == 2]:
			for (a, b) in [self.names[n]['childof'], self.names[n]['childof'][::-1]]:
				if self.names[a]['sex'] and (not self.names[b]['sex']):
					self.names[b]['sex'] = 'f' if self.names[a]['sex'] == 'm' else 'm'
					self.updatesex()

	def setsex(self, name, sex):
		if name not in self.names:
			self.names[name] = {'sex': '', 'parentof': [], 'childof': []}
		if not self.names[name]['sex']:
			self.names[name]['sex'] = sex
			self.updatesex()
		return self.names[name]['sex'] == sex

	def set_parent_of(self, c, p):
		for n in [c, p]:
			if n not in self.names:
				self.names[n] = {'sex': '', 'parentof': [], 'childof': []}
		if p in self.names[c]['childof']:
			return True
		if c == p or len(self.names[c]['childof']) == 2:
			return False
		for (tree, direction, name) in [(self.names[c]['parentof'], 'parentof', p), (self.names[p]['childof'], 'childof', c)]:
			while tree:
				if name in tree:
					return False
				tree = [e for d in tree for e in self.names[d][direction]]
		if len(self.names[c]['childof']) == 1:
			(old_p, new_sex) = (self.names[c]['childof'][0], self.names[p]['sex'])
			if new_sex + self.names[old_p]['sex'] in ['mm', 'ff']:
				return False
			couples = {tuple(self.names[n]['childof']) for n in self.names if len(self.names[n]['childof']) > 1} | {tuple((old_p, p))}
			S = {p: new_sex or 'm'}
			while any((parent in S for couple in couples for parent in couple)):
				newcouples = []
				for (a, b) in couples:
					if a in S or b in S:
						if b not in S:
							S[b] = 'f' if S[a] == 'm' else 'm'
						if a not in S:
							S[a] = 'f' if S[b] == 'm' else 'm'
						if S[a] == S[b]:
							return False
					else:
						newcouples.append((a, b))
				couples = newcouples
		self.names[p]['parentof'] += [c]
		self.names[c]['childof'] += [p]
		self.updatesex()
		return True


class Person:

	def __init__(self, name, my_family, gender='A'):
		self.name = name
		self.children = []
		self.parents = []
		self.cluster = {self}
		self.gender = gender
		my_family.known_persons[name] = self

class family:

	def __init__(self):
		self.known_persons = {}

	@staticmethod
	def __opposite_gender__(gender):
		return {'M': 'F', 'F': 'M', 'A': 'B', 'B': 'A'}[gender]

	def __define_gender__(self, person, gender):
		if person in self.known_persons:
			if self.known_persons[person].gender in ('A', 'B'):
				original_gender = self.known_persons[person].gender
				opposite_new_gender = family.__opposite_gender__(gender)
				for p in self.known_persons[person].cluster:
					p.gender = gender if p.gender == original_gender else opposite_new_gender
			else:
				return self.known_persons[person].gender == gender
		else:
			self.known_persons[person] = Person(person, gender=gender, my_family=self)
		return True

	def male(self, person):
		return self.__define_gender__(person, 'M')

	def female(self, person):
		return self.__define_gender__(person, 'F')

	def is_male(self, person):
		return person in self.known_persons and self.known_persons[person].gender == 'M'

	def is_female(self, person):
		return person in self.known_persons and self.known_persons[person].gender == 'F'

	def __is_ancestor_of__(self, p1, p2):
		if p1 == p2:
			return True
		elif len(p1.children) == 0:
			return False
		for c in p1.children:
			if self.__is_ancestor_of__(c, p2):
				return True
		return False

	@staticmethod
	def __join_cluster__(old_cluster, new_cluster, source_gender, target_gender, modify_genders=True):
		for p in old_cluster:
			if modify_genders:
				if p.gender == target_gender:
					p.gender = family.__opposite_gender__(source_gender)
				else:
					p.gender = source_gender
			new_cluster.add(p)
			p.cluster = new_cluster

	def set_parent_of(self, child, parent):
		if child == parent:
			return False
		if child not in self.known_persons:
			p = self.known_persons[parent] if parent in self.known_persons else Person(parent, my_family=self)
			c = Person(child, my_family=self)
		else:
			c = self.known_persons[child]
			if parent not in self.known_persons:
				if len(c.parents) >= 2:
					return False
				p = Person(parent, my_family=self)
				if len(c.parents) == 1:
					family.__join_cluster__(p.cluster, c.parents[0].cluster, c.parents[0].gender, p.gender)
			else:
				p = self.known_persons[parent]
				if c in p.children:
					return True
				if len(c.parents) >= 2:
					return False
				if self.__is_ancestor_of__(c, p):
					return False
				if len(c.parents) == 1:
					other_parent = c.parents[0]
					if other_parent.cluster == p.cluster or (other_parent.gender in ('M', 'F') and p.gender in ('M', 'F')):
						if other_parent.gender == p.gender:
							return False
						elif other_parent.cluster != p.cluster:
							family.__join_cluster__(p.cluster, other_parent.cluster, other_parent.gender, p.gender, modify_genders=False)
					elif p.gender in ('A', 'B'):
						family.__join_cluster__(p.cluster, other_parent.cluster, other_parent.gender, p.gender)
					elif other_parent.gender in ('A', 'B'):
						family.__join_cluster__(other_parent.cluster, p.cluster, p.gender, other_parent.gender)
					else:
						print('add_parent: unknown gender combination')
						return False
		c.parents.append(p)
		p.children.append(c)
		return True

	def get_parents_of(self, person):
		return sorted([p.name for p in self.known_persons[person].parents]) if person in self.known_persons else []

	def get_children_of(self, person):
		return sorted([c.name for c in self.known_persons[person].children]) if person in self.known_persons else []


from enum import Enum

class Gender(Enum):
	FEMALE = 1
	MALE = 2

	@staticmethod
	def opp_gender(gender):
		opp = {Gender.MALE: Gender.FEMALE, Gender.FEMALE: Gender.MALE}
		return opp[gender]

class Person:

	def __init__(self, name):
		self.name = name
		self.gender = None
		self.children = []
		self.parents = []

	def __copy__(self):
		copy = Person(self.name)
		copy.gender = self.gender
		copy.children = self.children.copy()
		copy.parents = self.parents.copy()
		return copy

	def __str__(self):
		return 'Name: {}, Gender: {}, Children: {}, Parents: {}'.format(self.name, self.gender, self.children, self.parents)

class Family:

	def __init__(self):
		self.family = dict()

	def __copy__(self):
		copy = Family()
		copy.family = {name: person.__copy__() for (name, person) in list(self.family.items())}
		return copy

	def __str__(self):
		return '\n' + '\n'.join((person.__str__() for (name, person) in list(self.family.items()))) + '\n'

	def init_if_missing(self, name):
		if name not in self.family:
			self.family[name] = Person(name)

	def set_gender(self, name, gender):
		self.init_if_missing(name)
		if self.family[name].gender == gender:
			return True
		elif self.family[name].gender == Gender.opp_gender(gender):
			return False
		else:
			for child in self.family[name].children:
				for parent in self.family[child].parents:
					if parent != name and self.family[parent].gender == gender:
						return False
			self.family[name].gender = gender
			for child in self.family[name].children:
				self.update_parent_of(child)
			return True

	def male(self, name):
		return self.set_gender(name, Gender.MALE)

	def is_male(self, name):
		self.init_if_missing(name)
		return self.family[name].gender == Gender.MALE

	def female(self, name):
		return self.set_gender(name, Gender.FEMALE)

	def is_female(self, name):
		self.init_if_missing(name)
		return self.family[name].gender == Gender.FEMALE

	def set_parent_of(self, child_name, parent_name):
		self.init_if_missing(child_name)
		self.init_if_missing(parent_name)
		current_parents = self.get_parents_of(child_name)
		if parent_name in current_parents:
			return True
		elif parent_name == child_name or child_name in self.get_ancestors_of(parent_name) or 2 <= len(current_parents) or (len(current_parents) == 1 and self.family[parent_name].gender is not None and (self.family[current_parents[0]].gender == self.family[parent_name].gender)):
			return False
		else:
			if len(current_parents) == 1 and self.family[parent_name].gender is None and (self.family[current_parents[0]].gender is None):
				family_copy = self.__copy__()
				res = family_copy.female(parent_name)
				if res:
					res = family_copy.set_parent_of(child_name, parent_name)
					if not res:
						return False
			self.update_parent_of(child_name, parent_name)
			return True

	def update_parent_of(self, child_name, parent_name=None):
		if parent_name is not None:
			self.family[child_name].parents.append(parent_name)
			self.family[parent_name].children.append(child_name)
			self.family[parent_name].children.sort()
		if len(self.family[child_name].parents) == 2:
			self.family[child_name].parents.sort()
			(p0, p1) = (self.family[self.family[child_name].parents[0]], self.family[self.family[child_name].parents[1]])
			if p0.gender is not None and p1.gender is not None or (p0.gender is None and p1.gender is None):
				return
			if p0.gender is not None:
				self.family[self.family[child_name].parents[1]].gender = Gender.opp_gender(p0.gender)
				for child in p1.children:
					if child != child_name:
						self.update_parent_of(child, None)
			elif p1.gender is not None:
				self.family[self.family[child_name].parents[0]].gender = Gender.opp_gender(p1.gender)
				for child in p0.children:
					if child != child_name:
						self.update_parent_of(child, None)

	def get_children_of(self, name):
		self.init_if_missing(name)
		return self.family[name].children.copy()

	def get_parents_of(self, name):
		self.init_if_missing(name)
		return self.family[name].parents.copy()

	def get_ancestors_of(self, name):
		self.init_if_missing(name)
		parents = self.get_parents_of(name)
		ln = len(parents)
		for parent in parents[:ln]:
			parents.extend(self.get_ancestors_of(parent))
		return parents


class Person:

	def __init__(self):
		self.sex = None
		self.children = []
		self.parents = []

class Family:

	def __init__(self):
		self.members = dict()

	def get_parents_gap(self, first, second):
		if first not in self.members or second not in self.members:
			return None
		kids = self.members[first].children[:]
		(parents, step) = ([first], 0)
		while kids:
			parents_size = len(parents)
			for kid in kids:
				parents.extend([p for p in self.members[kid].parents if p not in parents])
			del parents[:parents_size]
			if second in parents:
				return step
			kids_size = len(kids)
			for parent in parents:
				kids.extend([k for k in self.members[parent].children if k not in kids])
			del kids[:kids_size]
			step += 1
		return None

	def get_parent_sex(self, name):
		kids = self.members.get(name, Person()).children[:]
		(parents, kid_step) = ([name], 0)
		while kids:
			parents_size = len(parents)
			for kid in kids:
				parents.extend([p for p in self.members[kid].parents if p not in parents])
			del parents[:parents_size]
			kids_size = len(kids)
			for parent in parents:
				person = self.members[parent]
				if person.sex == 'male':
					return 'male' if kid_step % 2 else 'female'
				elif person.sex == 'female':
					return 'female' if kid_step % 2 else 'male'
				kids.extend([k for k in person.children if k not in kids])
			del kids[:kids_size]
			kid_step += 1
		return None

	def male(self, name):
		person = self.members.get(name, Person())
		if person.sex == 'female':
			return False
		elif person.sex is None:
			if self.get_parent_sex(name) == 'female':
				return False
			person.sex = 'male'
			self.members[name] = person
		return True

	def is_male(self, name):
		if self.members.get(name, Person()).sex == 'male':
			return True
		return self.get_parent_sex(name) == 'male'

	def female(self, name):
		person = self.members.get(name, Person())
		if person.sex == 'male':
			return False
		elif person.sex is None:
			if self.get_parent_sex(name) == 'male':
				return False
			person.sex = 'female'
			self.members[name] = person
		return True

	def is_female(self, name):
		if self.members.get(name, Person()).sex == 'female':
			return True
		return self.get_parent_sex(name) == 'female'

	def set_parent_of(self, child_name, parent_name):
		if child_name == parent_name:
			return False
		child = self.members.get(child_name, Person())
		parent = self.members.get(parent_name, Person())
		if child_name in parent.children:
			return True
		elif len(child.parents) == 2:
			return False
		kids = child.children[:]
		while kids:
			if parent_name in kids:
				return False
			for _ in range(len(kids)):
				kids.extend(self.members[kids.pop(0)].children)
		fp_sex = None
		if child.parents:
			fp_sex = self.members[child.parents[0]].sex
			if fp_sex is None:
				fp_sex = self.get_parent_sex(child.parents[0])
		sp_sex = self.get_parent_sex(parent_name) if parent.sex is None else parent.sex
		if fp_sex == sp_sex and fp_sex is not None:
			return False
		if fp_sex is None and sp_sex is None and child.parents and (parent_name in self.members):
			gap = self.get_parents_gap(child.parents[0], parent_name)
			if gap is not None and gap % 2:
				return False
		child.parents.append(parent_name)
		parent.children.append(child_name)
		self.members[child_name] = child
		self.members[parent_name] = parent
		return True

	def get_children_of(self, name):
		return sorted(self.members.get(name, Person()).children)

	def get_parents_of(self, name):
		return sorted(self.members.get(name, Person()).parents)


class Person:

	def __init__(self, name):
		self.name = name
		self.parents = set()
		self.children = set()
		self.gender = 0

	def is_ancestor_of(self, person):
		ancestors = set()
		generation = set([person])
		while len(generation):
			ancestors = ancestors.union(generation)
			next_generation = set()
			for ancestor in generation:
				if self in ancestor.parents:
					return True
				next_generation = next_generation.union(ancestor.parents)
			generation = next_generation

class Transaction(list):

	def __init__(self):
		list.__init__(self)

	def start(self):
		self.append(lambda : None)

	def end(self, commit):
		if commit:
			self.log(self.pop())
		else:
			self.pop()()
		return commit

	def log(self, undo):
		if not len(self):
			self.start()
		self.append((lambda rest: lambda : (undo(), rest()))(self.pop()))

class Family:

	def __init__(self):
		self.people = {}
		self.transaction = Transaction()

	def _member(self, name):
		if not name in self.people:
			self.people[name] = Person(name)
		return self.people[name]

	def set_parent_of(self, child, parent):
		if child == parent:
			return False
		child = self._member(child)
		parent = self._member(parent)
		if parent in child.parents:
			return True
		self.transaction.start()
		child.parents.add(parent)
		parent.children.add(child)
		self.transaction.log(lambda : (child.parents.remove(parent), parent.children.remove(child)))
		success = not child.is_ancestor_of(parent) and self._rule_parents(child)
		self.transaction.end(success)
		return success

	def male(self, person):
		return self._set_gender_of(self._member(person), 1)

	def is_male(self, person):
		return self._member(person).gender == 1

	def female(self, person):
		return self._set_gender_of(self._member(person), -1)

	def is_female(self, person):
		return self._member(person).gender == -1

	def get_children_of(self, person):
		return sorted([p.name for p in self._member(person).children])

	def get_parents_of(self, person):
		return sorted([p.name for p in self._member(person).parents])

	def _rule_parents(self, child):
		if len(child.parents) != 2:
			return len(child.parents) < 2
		female = [person for person in child.parents if person.gender == -1]
		male = [person for person in child.parents if person.gender == 1]
		undetermined = [person for person in child.parents if person.gender == 0]
		if not len(undetermined):
			return len(child.parents) < 2 or len(male) | len(female) == 1
		if len(undetermined) < len(child.parents):
			return self._set_gender_of(undetermined[0], len(female) - len(male))
		self.transaction.start()
		success = self._set_gender_of(undetermined[0], 1)
		self.transaction.end(0)
		return success

	def _set_gender_of(self, person, gender):
		if person.gender == gender:
			return True
		if person.gender == -gender:
			return False
		person.gender = gender
		self.transaction.log(lambda : setattr(person, 'gender', 0))
		return all((self._rule_parents(child) for child in person.children))


class Family(dict):

	def __init__(self):
		super().__init__()

	def __getitem__(self, name):
		if name in self:
			return super().__getitem__(name)
		ret = self[name] = Ppl(name)
		return ret

	def __setitem__(self, name, ppl):
		if name in self:
			raise Exception(f'cannot reassign a member of the family: {name}, {ppl}')
		super().__setitem__(name, ppl)

	def female(self, name):
		return self.male(name, isMale=False)

	def male(self, name, isMale=True):
		who = self[name]
		if who.hasGender() and isMale != who.isMale:
			return False
		who.isMale = isMale
		ok = all((c.updateGenders() for c in who.children))
		if not ok:
			who.isMale = None
		return ok

	def is_male(self, name):
		p = self[name]
		return p.hasGender() and p.isMale

	def is_female(self, name):
		p = self[name]
		return p.hasGender() and (not p.isMale)

	def get_children_of(self, name):
		return sorted((p.name for p in self[name].children))

	def get_parents_of(self, name):
		return sorted((p.name for p in self[name].parents))

	def set_parent_of(self, *childParent):
		(c, p) = (self[x] for x in childParent)
		return c.set_parent(p)
family = Family

class Ppl:

	def __init__(self, name, isMale=None):
		self.name = name
		self.isMale = isMale
		self.children = []
		self.parents = []

	def __eq__(self, o):
		return isinstance(o, self.__class__) and o.name == self.name

	def __hash__(self):
		return hash(self.name)

	def __repr__(self):
		return f'Ppl({self.name},{self.isMale} ; p={[p.name for p in self.parents]}, c={[p.name for p in self.children]})'

	def hasGender(self):
		return self.isMale is not None

	def has2Parents(self):
		return len(self.parents) == 2

	def acyclic(self, target, seens=None):
		if seens is None:
			seens = set()
		if target in seens:
			return False
		if self in seens:
			return True
		return seens.add(self) or all((c.acyclic(target, seens) for c in self.children))

	def set_parent(self, p):
		if p in self.parents:
			return True
		if self.has2Parents() or self == p:
			return False
		self.parents.append(p)
		p.children.append(self)
		if self.acyclic(p) and self.updateGenders():
			return True
		self.parents.pop()
		p.children.pop()
		return False

	def updateGenders(self, seensC=None, tome=()):
		if not self.has2Parents():
			return True
		(a, b) = self.parents
		if b.hasGender() or b in tome:
			(a, b) = (b, a)
		nG = a.hasGender() + b.hasGender()
		if seensC is None:
			(seensC, tome) = (set(), {})
			if not nG:
				tome[a] = 1
				return all((c.updateGenders(seensC, tome) for c in a.children if c not in seensC))
		seensC.add(self)
		if nG == 2:
			return a.isMale ^ b.isMale
		if a in tome and b in tome:
			return tome[a] ^ tome[b]
		if nG == 1:
			b.isMale = not a.isMale
		elif a in tome:
			tome[b] = 1 ^ tome[a]
		isOK = all((c.updateGenders(seensC, tome) for c in b.children if c not in seensC))
		if not isOK and nG == 1:
			b.isMale = None
		return isOK


from collections import defaultdict

class family:

	def __init__(self):
		self.males = set()
		self.females = set()
		self.parents = defaultdict(lambda : set())
		self.children = defaultdict(lambda : set())

	def male(self, name):
		if name in self.females:
			return False
		if name in self.males:
			return True
		safe_copy = self.males.copy()
		self.males.add(name)
		for child in self.parents[name]:
			partners = self.children[child] - {name}
			for partner in partners:
				if not self.female(partner):
					self.males = safe_copy
					return False
		return True

	def is_male(self, name):
		return name in self.males

	def female(self, name):
		if name in self.males:
			return False
		if name in self.females:
			return True
		safe_copy = self.females.copy()
		self.females.add(name)
		for child in self.parents[name]:
			partners = self.children[child] - {name}
			for partner in partners:
				if not self.male(partner):
					self.females = safe_copy
					return False
		return True

	def is_female(self, name):
		return name in self.females

	def set_parent_of(self, child_name, parent_name):
		if child_name == parent_name:
			return False
		parents = self.children[parent_name]
		while parents:
			if child_name in parents:
				return False
			new_parents = set()
			for parent in parents:
				new_parents |= self.children[parent]
			parents = new_parents
		current_parents = self.children[child_name]
		if parent_name in current_parents:
			return True
		if len(current_parents) >= 2:
			return False
		new_parents = current_parents | {parent_name}
		if len(new_parents & self.males) > 1 or len(new_parents & self.females) > 1:
			return False
		self.parents[parent_name].add(child_name)
		self.children[child_name].add(parent_name)
		if len(new_parents) == 2:
			for parent in new_parents:
				if self.is_male(parent):
					if not self.female(next(iter(new_parents - {parent}))):
						return False
				elif self.is_female(parent):
					if not self.male(next(iter(new_parents - {parent}))):
						return False
			if len(new_parents & (self.males | self.females)) == 0:
				new_parents = list(new_parents)
				for (try_father, try_mother) in [new_parents, new_parents[::-1]]:
					(safe_males_copy, safe_females_copy) = (self.males.copy(), self.females.copy())
					conflict_assign_gender = not self.male(try_father) or not self.female(try_mother)
					(self.males, self.females) = (safe_males_copy, safe_females_copy)
					if conflict_assign_gender:
						return False
		return True

	def get_children_of(self, name):
		return sorted(self.parents[name])

	def get_parents_of(self, name):
		return sorted(self.children[name])


from collections import deque
from enum import Enum

class Gender(Enum):
	Male = 'M'
	Female = 'F'

class Member:

	def __init__(self, name):
		self.name = name
		self.parents = []
		self.children = []
		self.spouse = None
		self.gender = None

	def __eq__(self, other):
		return self.name == other.name

	def __hash__(self):
		return hash(self.name)

	def __repr__(self):
		return f"[{self.name}|{self.gender}<=>{(self.spouse.name if self.spouse is not None else '?')}: {list(map(lambda c: c.name, self.children))}]"

	def set_gender(self, gender):
		if self.gender is not None and gender != self.gender:
			return False
		if self.spouse is not None:
			if self.spouse.gender == gender:
				return False
			elif gender == Gender.Male:
				self.spouse.gender = Gender.Female
			else:
				self.spouse.gender = Gender.Male
		if self.gender is None:
			self.gender = gender
		return True

	def set_parent(self, parent):
		if parent not in self.parents:
			self.set_spouse(parent)
			self.parents.append(parent)

	def set_spouse(self, parent):
		if len(self.parents) == 1:
			current_parent = self.parents[0]
			parent.spouse = current_parent
			current_parent.spouse = parent

	def set_child(self, child):
		if child not in self.children:
			self.children.append(child)

class family:

	def __init__(self):
		self.members = []

	def is_male(self, name):
		member = self.add_member(name)
		return True if member.gender == Gender.Male else False

	def is_female(self, name):
		member = self.add_member(name)
		return True if member.gender == Gender.Female else False

	def male(self, name):
		member = self.add_member(name)
		if member.set_gender(Gender.Male):
			self.update_genders()
			return True
		else:
			return False

	def female(self, name):
		member = self.add_member(name)
		if member.set_gender(Gender.Female):
			self.update_genders()
			return True
		else:
			return False

	def set_parent_of(self, child_name, parent_name):
		child = self.add_member(child_name)
		parent = self.add_member(parent_name)
		if not self.valid_relationship(child, parent):
			return False
		child.set_parent(parent)
		parent.set_child(child)
		self.update_genders()
		return True

	def update_genders(self):
		for m in self.members:
			if m.spouse is not None and m.spouse.gender is not None:
				if m.spouse.gender == Gender.Male:
					m.gender = Gender.Female
				else:
					m.gender = Gender.Male

	def get_children_of(self, name):
		member = self.add_member(name)
		return sorted(list([m.name for m in member.children]))

	def get_parents_of(self, name):
		member = self.add_member(name)
		return sorted(list([m.name for m in member.parents]))

	def valid_relationship(self, child, parent):
		if child == parent:
			return False
		if child in parent.children:
			return True
		if not self.check_children_of_children(child, parent):
			return False
		if len(child.parents) >= 2:
			return False
		if len(child.parents) == 1:
			current_parent = child.parents[0]
			if current_parent.gender == parent.gender and current_parent.gender is not None:
				return False
		if not self.check_gender_assignment(child, parent):
			return False
		return True

	def check_gender_assignment(self, child, parent):
		visited = set()
		queue = deque([parent])
		visited.add(parent)
		counter = 1
		while queue:
			p = queue.popleft()
			if len(p.children) == 0:
				continue
			for c in p.children:
				if c not in visited:
					visited.add(p)
					for pp in c.parents:
						if pp not in visited:
							visited.add(pp)
							queue.append(pp)
							if pp.gender is None:
								counter += 1
			if child in p.children:
				if counter > 2:
					if counter % 2 != 0 or counter > 5:
						return False
		return True

	def check_children_of_children(self, child, parent):
		visited = set()
		queue = deque([child])
		visited.add(child)
		while queue:
			c = queue.popleft()
			if len(c.children) == 0:
				continue
			for cc in c.children:
				if cc == parent:
					return False
				if cc not in visited:
					visited.add(cc)
					queue.append(cc)
		return True

	def add_member(self, name):
		new_member = Member(name)
		if new_member not in self.members:
			self.members.append(new_member)
		return self.members[self.members.index(new_member)]


from collections import defaultdict, deque
from copy import deepcopy

class Member:

	def __init__(self, name, gender=''):
		self.name = name
		self.gender = gender

	def __repr__(self):
		return self.name

class family:

	def __init__(self):
		self.children = defaultdict(list)
		self.member_objects = []

	def get_member(self, name):
		member = next((i for i in self.member_objects if i.name == name), None)
		if member is None:
			self.member_objects.append(Member(name))
			return self.member_objects[-1]
		return member

	def male(self, name):
		member = self.get_member(name)
		if member.gender == 'female':
			return False
		member.gender = 'male'
		self.set_rest_of_things()
		return True

	def is_male(self, name):
		gdr = self.get_member(name).gender
		return bool(gdr) and gdr == 'male'

	def female(self, name):
		member = self.get_member(name)
		if member.gender == 'male':
			return False
		member.gender = 'female'
		self.set_rest_of_things()
		return True

	def is_female(self, name):
		gdr = self.get_member(name).gender
		return bool(gdr) and gdr == 'female'

	def is_cycle(self, child, parent):
		copy = defaultdict(list, {i.name: [k.name for k in j] for (i, j) in self.children.items()})
		copy[child.name].append(parent.name)
		Q = deque([[parent.name, []]])
		while Q:
			(node, path) = Q.popleft()
			path.append(node)
			for neighbour in copy[node]:
				if neighbour not in path:
					Q.append([neighbour, path[:]])
				elif neighbour == parent.name:
					return True
		return False

	def is_consistent(self, child, parent):
		if self.is_cycle(child, parent):
			return True
		temp = Member('GG')
		self.children[child].append(temp)
		copy = deepcopy(self.children)
		self.children[child].remove(temp)
		nodes = set([i for i in copy] + [j for i in copy.values() for j in i])
		for i in nodes:
			i.gender = ''
		prt = next((i for i in nodes if i.name == parent.name), None)
		if not prt:
			return False
		prt.gender = 'male'
		k = self.set_rest_of_things(copy, prt)
		return 'malefemale' in k or 'femalemale' in k

	def set_parent_of(self, child, parent):
		(child, parent) = (self.get_member(child), self.get_member(parent))
		if parent in self.children[child] or parent in self.children[child]:
			return True
		if child == parent or len(self.children[child]) == 2 or (parent.gender and self.children[child] and (self.children[child][0].gender == parent.gender)) or self.is_consistent(child, parent):
			return False
		self.children[child].append(parent)
		self.set_rest_of_things()
		return True

	def get_children_of(self, name):
		return sorted([i.name for (i, j) in self.children.items() if name in [k.name for k in j]])

	def get_parents_of(self, name):
		return sorted(next(([k.name for k in j] for (i, j) in self.children.items() if i.name == name), []))

	def set_rest_of_things(self, cpy='', prt=''):
		cpy = self.children if not cpy else cpy
		(d, i, keys, genders) = ({'male': 'female', 'female': 'male'}, 0, list(cpy.keys()), defaultdict(str))
		while i < len(keys):
			parents = cpy[keys[i]]
			if len(parents) > 1:
				(a, b) = parents
				if (a.gender, b.gender).count('') == 1:
					b.gender = d.get(a.gender, b.gender)
					a.gender = d.get(b.gender, a.gender)
					genders[a.name] = a.gender
					genders[b.name] = b.gender
					i = -1
			i += 1
		return genders[prt.name] + genders['GG'] if prt else ''


from collections import defaultdict
from copy import deepcopy

class family:

	def __init__(self):
		self.fam = defaultdict(lambda : defaultdict(set))

	def male(self, name):
		return self.change_gender(name, 'male')

	def is_male(self, name):
		return self.fam[name]['gender'] == 'male'

	def female(self, name):
		return self.change_gender(name, 'female')

	def is_female(self, name):
		return self.fam[name]['gender'] == 'female'

	def set_parent_of(self, child_name, parent_name):
		if parent_name in self.fam[child_name]['parents']:
			return True
		if not self.check_parent(child_name, parent_name):
			return False
		res = True
		if self.fam[child_name]['parents']:
			other = next(iter(self.fam[child_name]['parents']))
			if self.fam[parent_name]['gender']:
				if self.fam[other]['gender']:
					res = self.fam[parent_name]['gender'] != self.fam[other]['gender']
				else:
					res = self.change_gender(other, family.opposite(self.fam[parent_name]['gender']))
			elif self.fam[other]['gender']:
				res = self.change_gender(parent_name, family.opposite(self.fam[other]['gender']))
			else:
				save = deepcopy(self.fam)
				self.fam[child_name]['parents'].add(parent_name)
				self.fam[parent_name]['children'].add(child_name)
				res = self.check_gender(parent_name) and self.check_gender(other)
				if not res:
					self.fam = save
				return res
		if res:
			self.fam[child_name]['parents'].add(parent_name)
			self.fam[parent_name]['children'].add(child_name)
		return res

	def get_children_of(self, name):
		return sorted(self.fam[name]['children'])

	def get_parents_of(self, name):
		return sorted(self.fam[name]['parents'])

	def change_gender(self, name, gender):
		save = deepcopy(self.fam)
		if not self.update_gender(name, gender):
			self.fam = save
			return False
		return True

	def search_ancestors(self, name, search):
		if name == search:
			return True
		return any((self.search_ancestors(parent, search) for parent in self.fam[name]['parents']))

	def update_gender(self, name, gender):
		if self.fam[name]['gender']:
			return self.fam[name]['gender'] == gender
		self.fam[name]['gender'] = gender
		for child in self.fam[name]['children']:
			if len(self.fam[child]['parents']) == 2:
				other = next((p for p in self.fam[child]['parents'] if p != name))
				if not self.update_gender(other, family.opposite(gender)):
					return False
		return True

	def check_gender(self, name):
		save = deepcopy(self.fam)
		res = self.update_gender(name, 'male')
		self.fam = save
		if res:
			return True
		save = deepcopy(self.fam)
		res = self.update_gender(name, 'female')
		self.fam = save
		return res

	def check_parent(self, child, parent):
		if child == parent:
			return False
		if len(self.fam[child]['parents']) == 2:
			return False
		if self.search_ancestors(parent, child):
			return False
		return True

	@staticmethod
	def opposite(gender):
		return 'female' if gender == 'male' else 'male'