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!

Difficulty: interview

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):
        # Create child and/or parent if they do not exist
        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
        
        # descendants and ancestors     
        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                

            # Check for clashing parents
            # Get all couple and create a putative sex dictionary S
            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      # string
        self.children = []    # list of person objects
        self.parents = []     # list of person objects
        # A cluster represents a subset of a family partitioned by the
        # transitive closure of the relationship 'has a child in common with'
        self.cluster = {self, }
        self.gender = gender  # will be 'A' if unknown
        my_family.known_persons[name] = self


class family:
    def __init__(self):
        # Dictionary mapping names to person objects
        self.known_persons = {}

    # The letters M and F stand for 'known to be male' and 'known to be female'. The
    # letters A and B represent opposite genders within each cluster, but it is not
    # known which of the two letters represents male or female for that cluster.
    @staticmethod
    def __opposite_gender__(gender):
        return {'M': 'F', 'F': 'M', 'A': 'B', 'B': 'A'}[gender]

    # A common implementation of the mandatory methods 'male' and 'female'
    def __define_gender__(self, person, gender):
        if person in self.known_persons:
            if self.known_persons[person].gender in ('A', 'B'):
                # We are now able to fill in the correct gender not only for
                # this person, but for all the members of its cluster
                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:
                # Gender already known: check consistency
                return self.known_persons[person].gender == gender
        else:
            # First time we hear about this person; create them
            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'

    # Auxiliary method to test for cycles in family trees
    def __is_ancestor_of__(self, p1, p2):
        if p1 == p2:
            return True
        elif len(p1.children) == 0:
            return False
        # Recursion: if one of my children is an ancestors of p2, then so am I
        for c in p1.children:
            if self.__is_ancestor_of__(c, p2):
                return True
        return False

    # Auxiliary method to join 2 existing clusters after a member of each of them
    # have acquired a common child, and to optionally adjust unknown genders in 1 of the clusters
    # based on the genders in the other cluster (which may be known or unknown)
    @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 still unknown, but opposite of target_gender
                    p.gender = source_gender
            new_cluster.add(p)
            p.cluster = new_cluster

    # This method is the crux because despite its simple name, it has multiple functions:
    # - check/update parent-child relationships including cycles
    # - create 0, 1 or 2 new persons
    # - join existing clusters if necessary
    # We define different procedures depending on whether child and/or parent existed yet
    def set_parent_of(self, child, parent):
        # Eliminate a silly test case
        if child == parent:
            return False
        if child not in self.known_persons:
            # The child is new.
            p = self.known_persons[parent] if parent in self.known_persons else Person(parent, my_family=self)
            c = Person(child, my_family=self)
        else:
            # The child exists. Darn.
            c = self.known_persons[child]
            if parent not in self.known_persons:
                # New parent, existing child
                if len(c.parents) >= 2:
                    # Can't have 3 parents
                    return False
                p = Person(parent, my_family=self)
                if len(c.parents) == 1:
                    # Child already had a parent: put the new parent in the same cluster as the existing parent
                    family.__join_cluster__(p.cluster, c.parents[0].cluster, c.parents[0].gender, p.gender)
            else:
                # Both child and parent were known
                p = self.known_persons[parent]
                if c in p.children:
                    # Parent/child relationship was already known: do nothing
                    return True
                if len(c.parents) >= 2:
                    # p wasn't your parent yet and you can't have 3 parents
                    return False
                if self.__is_ancestor_of__(c, p):
                    # Can't have a cycle in the ol' family tree
                    return False
                if len(c.parents) == 1:
                    other_parent = c.parents[0]
                    # Child had 1 other parent: check gender compatibility between clusters;
                    # if necessary, join two clusters.
                    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:
                            # We already know that these 2 people have the same gender
                            # (perhaps even without knowing which gender it is)
                            # so they cannot become parents of the same child.
                            return False
                        elif other_parent.cluster != p.cluster:
                            # Consistent genders in different clusters:
                            # join the 2 clusters without modifying genders
                            family.__join_cluster__(p.cluster, other_parent.cluster,
                                                    other_parent.gender, p.gender,
                                                    modify_genders=False)
                    elif p.gender in ('A', 'B'):
                        # join 2 clusters, at most 1 of which has known genders
                        family.__join_cluster__(p.cluster, other_parent.cluster, other_parent.gender, p.gender)
                    elif other_parent.gender in ('A', 'B'):
                        # Join 2 clusters, exactly 1 of which had known genders: transfer that knowledge
                        family.__join_cluster__(other_parent.cluster, p.cluster, p.gender, other_parent.gender)
                    else:
                        print("add_parent: unknown gender combination")
                        return False
        # Finally do what we came here for
        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 there is another parent with known gender, checks for inconsistency
            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))
        # Two possibilities: try one just to see if it leads to a gender-inconsistency
        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
        
            

"""
def logger(f):
    @wraps(f)
    def wrapper(self, *a,**kw):
        print('-------')
        print(f.__name__, a, kw)
        print("\t"+"\n\t".join(map(str,self.values())))
        ret = f(self,*a,**kw)
        x = "\n\t\t".join(map(str,self.values()))
        print(f'***\n{f.__name__} returns: {ret}\nFinal state:\t{x}\n------\n')
        return ret
    return wrapper

from functools import wraps
from inspect import *

for name,f in getmembers(Family, predicate=isfunction):
    if not name.startswith('__'):
        setattr(Family, name, logger(f))
#"""

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
            else:
                if 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

    # BFS algorithm
    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

            # Detect cycle
            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"]))
            else:
                if 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"