Problem c Double np-hard Time limit. 2 second "Name and Class year Course to be Covered: (Course Number and Title) Reason for covering the course independently. Hami I ton College Appl ication for Independent Coverage of Course Work Definitions In this problem, a graph is a set of n vertices together with a set of m edges, where an edge is an unordered pair of different vertices(edges are undirected). The two vertices that comprise an edge are said to be that edges endpoints. a vertex cover of a given graph g is a subset c of its vertices, such that each edge of g has at least one of its endpoints in C. An independent set of a given graph G is a subset s of its vertices, such that no edge of g has both of its endpoints in The problem of finding a minimum vertex cover (that is, a vertex cover of the smallest possible size) for any graph is NP-hard. The problem of finding a maximum independent set of any graph is also NP-hard. That a formal way of saying that no one knows whether there exists an algorith that runs in time polynomial in n and solves any one of the two problems We want to define a class of problems that are even harder than the NP-hard problems. We are going to call them Double NP-hard"! Your job is to solve the first Double NP-hard problem Problem Given a graph G, find a subset C of its vertices that is both a minimum vertex cover and a maximum independent set Input The first line of input gives the number of cases, N.n test cases follow. Each one starts with two lines containing n(0<=n<=1000) and m (0<=m<=100000)as above. The next m lines will each describe an edge of G as a pair of different vertices, which are numbered from i to n5 Problem C Double NP-hard Time Limit: 2 second "Name and Class Year: Course to be Covered: (Course Number and Title) Reason for covering the course independently:" Hamilton College Application for Independent Coverage of Course Work Definitions In this problem, a graph is a set of n vertices together with a set of m edges, where an edge is an unordered pair of different vertices (edges are undirected). The two vertices that comprise an edge are said to be that edge's endpoints. A vertex cover of a given graph G is a subset C of its vertices, such that each edge of G has at least one of its endpoints in C. An independent set of a given graph G is a subset S of its vertices, such that no edge of G has both of its endpoints in S. The problem of finding a minimum vertex cover (that is, a vertex cover of the smallest possible size) for any graph is NP-hard. The problem of finding a maximum independent set of any graph is also NP-hard. That is a formal way of saying that no one knows whether there exists an algorithm that runs in time polynomial in n and solves any one of the two problems. We want to define a class of problems that are even harder than the NP-hard problems. We are going to call them "Double NP-hard"! Your job is to solve the first Double NP-hard problem. Problem Given a graph G, find a subset C of its vertices that is both a minimum vertex cover and a maximum independent set. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing n (0<=n<=1000) and m (0<=m<=100000) as above. The next m lines will each describe an edge of G as a pair of different vertices, which are numbered from 1 to n