Given a list of members of a family and their interactions. We need to find whether this family is valid or not. A valid family is defined as if the members of a family are interacting with opposite sex.

For example, Given a family of 4 members and their relationship as follows:-

1 - 2
3 - 4
1 - 3
2 - 4

Its a valid family as we can consider
1-> male
2 -> female
3 -> female
4 -> male

but this is not valid

1 2
2 3
1 3

I have thought this as a graph and did bfs and find if there is any relationship in any of children of a node.