| Sex Assignments And Breeding Experiments |
Everyone is familiar with the pictorial representation of family trees. In these "pictures" one uses points and lines to represent family structures and interfamily relationships. Thus, if M and F are the parents of three children, two boys and one girl, we have the figure below:
The next figure might represent the inter-family relationship of two families
It is easy to conceive of a large number of such pictures. Some can represent family trees and some cannot. You are to consider the problem of characterizing those which can represent family trees. We will actually work in a simpler context than that of human relationships. Most human societies preclude family trees of the forms shown below.
It is, however, quite complicated to give conditions which would eliminate pictures of this sort. For simplicity, we suppose that we are dealing with a population which is completely characterized by the condition of bisexual reproduction (M & F). If the picture or graph is such that by a proper assignment of sexes to the members of the population, the picture represents the results of a breeding experiment which could theoretically take place, then we say the graph is sexy. Otherwise the graph is not sexy. You must write a program to examine an arbitrary directed graph and determine if it is sexy.
Input will be a series of descriptions of graphs in the following form:
An integer n indicating the number of nodes in the graph, followed by an integer m indicating the number of directed edges in the graph will appear on the first line of input. The next m lines of the file will each contain a pair x, y of integers in the range 1 - n. Each pair will represent a directed edge from node x to node y. Input is terminated by end-of-file.
For each graph in the input file, you will output the appropriate one of the following statements.
Graph number i is sexy
Graph number i is not sexy
The number i represents the number of the graph in the input file.
We are adopting the convention that the existence of a directed edge from x to y indicates that x is a parent of y. Further, each individual usually has exactly two parents. No individual can have two parents of the same sex or more than two parents. Breeding experiments do not extend into the indefinite past. A point is always reached where one or both of the parents of a member of the population are unknown. The nodes with no parents would appear on the top level of a sexy graph. Births of individuals are assumed to be sequential in time. Thus the following graph is not sexy.
5 6 1 3 2 3 1 4 2 4 1 5 2 5 3 3 1 2 2 3 3 1
Graph number 1 is sexy Graph number 2 is not sexy