Visiting friends

3.6

8 votes
Algorithms, Approved, Combinatorics, Depth First Search, Dynamic Programming, Graphs, Math, Medium, Ready, Recruit
Problem

M friendships exist between N people. They are divided into groups such that all the friends will remain in same group and the people from each group visit each other according to the following conditions:

  1. Each people can host only one other people from their group.
  2. Each people can visit only one other people from their group.
  3. Friendship is transitive in nature, which means, if A is a friend of B and B is a friend of C then A is also a friend of C.

Write a program to find the number of ways in which the people from each group can visit each other. Two ways are considered different if at least one people visits two different friends.

Input format

  • First line: T (number of test cases)
    For each test case
  • First line: Two space-separated integers N and M
  • Next M lines: Two space-separated integers U and V denoting a friendship between U and V

Output format

For each test case, first print the number of groups and in next line, print the number of ways in which the people from each group can visit each other, in decreasing order of number of ways.

Constraints

1T105
1N20
1MN×N

1U,VN

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

There are 2 groups: First group consists of {1,2,3} so the number of ways = 2, 1->2->3->1 and 1->3->2->1 where -> represent visit. Second group consists of {4,5} so the number of ways = 1, as friend 4 will visit friend 5 in his/her home and friend 5 will visit friend 4 in his/her home.

Editor Image

?