Given N student and Menemy relations. You need to divide these N students into 2 groups...

 

Transcribed Image Text:

Given N student and Menemy relations. You need to divide these N students into 2 groups of equal sizes S such that no two students with direct enemy relations are in the same group. You need to maximize the value of S. Also, it is guaranteed that no student will have enemy relations with more than 2 students. Notes . S is the number of students in a single group. . Both groups should have the same number of students .i.e S. Find the maximum possible value of S. Function description Complete the solve function. This function takes the following 3 parameters and returns the answer: • N: Represents a number of students • M: Represents the number of enemy relations • enemy. Represents the enemy relation Input format for custom testing Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code. • The first line contains an integer N. • The second line contains an integer M. • The next M line contains two space-separated integers, u, and v, representing the enemy relation between u and v. Output format Print the maximum possible value of S. Constraints 1 < M < N < 5 × 105 1 ≤ u, v<N Sample input ▷→> 6 4 1 2 24 15 63 1111 Sample output 3 Given N student and Menemy relations. You need to divide these N students into 2 groups of equal sizes S such that no two students with direct enemy relations are in the same group. You need to maximize the value of S. Also, it is guaranteed that no student will have enemy relations with more than 2 students. Notes . S is the number of students in a single group. . Both groups should have the same number of students .i.e S. Find the maximum possible value of S. Function description Complete the solve function. This function takes the following 3 parameters and returns the answer: • N: Represents a number of students • M: Represents the number of enemy relations • enemy. Represents the enemy relation Input format for custom testing Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code. • The first line contains an integer N. • The second line contains an integer M. • The next M line contains two space-separated integers, u, and v, representing the enemy relation between u and v. Output format Print the maximum possible value of S. Constraints 1 < M < N < 5 × 105 1 ≤ u, v<N Sample input ▷→> 6 4 1 2 24 15 63 1111 Sample output 3

Answer rating: 100% (QA)

Heres a Python function to solve the problem python def solveN M enemy adjlist ... View the full answer