Algorithms on graphs

Design a program that checks whether the given edge M set is a perfect matching for the given graph.

Input file format is similar to the input file format of the assignment 1, but for each edge in addition to the endpoints it is given ‘1’ for edges in M and ‘0’ for edges not in M.

Output file must contain only one line which can be either of the following strings:

The complete implementation of this assignment gives you 12 pts.