Partitioned Subgraph | MatCom Online Grader

The 5th Cuban Programming League (Real Contest)

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

H - Partitioned Subgraph

Languages: C++, Java, Python, Kotlin

Time & Memory limits: (details)

<p style='text-align: justify;'>
Juan is a math enthusiast and loves solving problems related to graph theory. Her Graph Theory professor, Mrs. Aguilar, has noticed his ability and has assigned him a particularly difficult problem. The problem consists of finding, given a graph, the largest subgraph that can be divided into two disjoint sets of vertices, in such a way that all the edges of the original graph that connect any pair of nodes of the subgraph must be in different sets.

Juan has been working hard on the problem for several days, but has not been able to find a solution. Therefore, he asks the Cuban Programming League for help to solve the following problem: given a graph with $N$ vertices and $M$ edges, find the subgraph with the largest vertex set in which the vertices of the graph can be divided into two disjoint sets so that all the edges connect a vertex from one set to another vertex of the opposite set. This subgraph will have all the edges of the original graph that connect any pair of nodes of the subgraph. The empty set is a valid set.
</p>

Input

Output

Sample test(s)

Input

4 4 1 2 2 3 2 4 3 4

Output

Input

2 0

Output

Matcom Online Grader

The 5th Cuban Programming League (Real Contest)

Ended

H - Partitioned Subgraph

Languages: C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)

Hints