Go Back
TE'S And Their Project Groups (100)
Description

Problem Author: Pritam Negi
Third year Engineering students are just about to finish their term of Semester 6. As they are nearing their entry into the final year of Engineering now they have been informed to form their project groups by the end of Semester 6.
Now the students want to include only those students in their project groups whom they have synergy with. Also the condition according to the university norms is that every project group must contain at least 2 members but not more than 4 members. So a project group is considered as valid if it satisfies the above condition.
The existence of synergy is mutual i.e. if student i has synergy with student j then student j has synergy with student i as well. Also the existence of synergy is transitive. This means that if student i is has synergy with student j AND student j has synergy with student k, then student i and student k will have synergy among each other.
This complicates the task for the Project Coordinator to determine the number of valid project groups that exist in the whole class. Hence she needs your help. Given the number of students and synergy list help project coordinator determine the number of valid project groups.

Input

The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and M, denoting the number of students and the number of synergy relations, respectively. Each of the following M lines contains two space-separated integers i and j, denoting student i and student j have synergy among themselves.

Output

For each test case, output a single line containing two space separated integers, denoting the maximum number of valid project groups that can be formed.

Constraints

1<= T <= 5
1<= N <= 105
1<= M <= 105
1 <= i,j <= N
i ≠ j
For any pair of student i and j such that 1 ≤ i < j ≤ N, at most one pair among (i, j) and (j, i) will appear in the input.

Example
Copy Input

Input:
2
4 2
1 2
2 3
6 3
1 2
3 4
5 6

Output:
1
3

Explanation

TEST CASE 1: In this case student 1 has synergy with student 2. Student 2 in turn has synergy with student 3. Hence student 1,2,3 can form a project group of 3 members. Student 4 has synergy with no other student hence cannot be considered as a valid project group. Hence only 1 valid project group exists in this case.

TEST CASE 2: In this case student 1 has synergy with student 2 so they can form a form a group of 2 members. Same goes for group of students 3, 4 and 5, 6. Hence 3 valid project groups exist in this case.

Good Bye Batch 15-19
#OneLastTime Contest from Batch of 2015-19 of SIES GST



Announcement
Surprise Problem Added!
Contest is extended by 24 hours!

Problem Tags
graphs

Supported by our Coding Partner