If we observe the given problem, we can model it in a graph, specifically a bipartite graph - G (X, Y), where ‘X’ is a vertex set of boys and ‘Y’ is vertex set of girls, and there an edge between a girl and boy if they can dance together. Now we just need to find a set with a maximum number of edges such that no two edges in the set have a common vertex. Here, we will use the concept of Maximum Bipartite Matching and the algorithm Hopcroft-Karp Algorithm. Hopcroft-Karp algorithms say that “A matching M is not maximum if there exists an augmenting path. . An augmenting path in a bipartite graph, with respect to some matching, is an alternating path whose initial and final vertices are unsaturated, i.e., they do not belong in the matching. Here, we will find out the augmenting paths. Whenever we get an augmenting path, we will remove it from our maximal matching ‘M’ and add nonmatching edges to ‘M’, and finally return ‘M’.

Algorithm:

• Initialize Maximum Matching M as null.
• Run a loop until there is no augmenting path in Graph.
  • Use BFS to build an alternating level graph, rooted at unmatched vertices in the ‘boy’ set
  • Augment current matching M with a maximal set of vertex disjoint shortest-length paths using DFS.
• Return M

O(N + M + K) where K is the potential pairs and N and M are the number of boys and girls respectively.

The Hopcroft-Karp algorithm takes O(N + M + K) space in the worst case for the BFS or DFS algorithm.

O(K * sqrt(N + M)) where K is the potential pairs and N and M are the number of boys and girls respectively.

Each iteration of the Hopcroft-Karp algorithm executes the breadth-first search and depth-first search once. This takes O(K) time. Since each iteration of the algorithm finds the maximal set of shortest augmenting paths by eliminating a path from a root to an unmatched edge, there are at most O(sqrt(N + M)) iterations needed in the worst case.

import java.util.*;

/*

    Time Complexity: O(K * sqrt(N + M))

    Space Complexity: O(N + M + K)



    Where K is the potential pairs and N and M are the number of boys and girls respectively.

*/



public class Solution

{

    // Array to store the results.

    public static ArrayList> result = new ArrayList>();

    

    // Graph to map the boy pair with girl.

    private static ArrayList[] graph;



    // Utility Arrays for bfs and dfs.

    private static int[] pairU, pair, distanceOfU, qq;





    // Bfs function to find agumented path

    private static boolean bfs(int n)

    {

        int head = 0;

        int cnt = 0;

        distanceOfU[0] = n;



        for(int u = 1; u <= n; u++)

        {

            if (pair[u] == 0)

            {

                distanceOfU[u] = 0;

                qq[head + cnt++] = u;

            }

            else

            {

                distanceOfU[u] = n;

            }

        }



        while (cnt > 0)

        {

            int u = qq[head++];

            cnt--;

            int d = distanceOfU[u] + 1;

            ArrayList adj = graph[u];



            for (int v : adj)

            {

                int w = pairU[v];

                if (distanceOfU[w] == n)

                {

                    distanceOfU[w] = d;

                    if (w == 0)

                    {

                        return true;

                    }



                    qq[head + cnt++] = w;

                }

            }

        }



        return false;

    }



    // Augment current matching M with a maximal set of vertex disjoint shortest-length paths using DFS

    private static boolean dfs(int n, int u)

    {

        if (u == 0)

        {

            return true;

        }



        int d = distanceOfU[u] + 1;

        ArrayList adj = graph[u];



        for(int v : adj)

        {

            int w = pairU[v];

            if(distanceOfU[w] == d && dfs(n, w))

            {

                pair[u] = v;

                pairU[v] = u;

                return true;

            }

        }



        distanceOfU[u] = n;

        return false;

    }





    private static void hopcroftKarp(int n, int m)

    {

        pair = new int[n + 1];

        pairU = new int[m + 1];

        distanceOfU = new int[n + 1];

        qq = new int[n];

        int c = 0;



        // Use BFS to build an alternating level graph, rooted at unmatched vertices in the boy set

        while (bfs(n))

        {

            for (int u = 1; u <= n; u++)

            {

                if (pair[u] == 0 && dfs(n, u))

                {

                    c++;

                }

            }

        }

    }



    public static ArrayList> danceTogether(int edges[][], int n, int m, int k)

    {

        graph = new ArrayList[n+1];



        for (int i = 1; i <= n; i++)

        {

            graph[i] = new ArrayList();

        }



        int i = 0;



        // Create Graph 

        while (k-- > 0)

        {

            int u = edges[i][0];

            int v = edges[i][1];

            graph[u].add(v);

            i++;

        }



        // Hopcroft_karp algorithm 

        hopcroftKarp(n, m);



        for (i = 1; i <= n; i++)

        {

            if (pair[i] != 0)

            {

                ArrayList temp = new ArrayList();

                temp.add(i);

                temp.add(pair[i]);

                result.add(temp);

            }

        }



        return result;

    }

}

'''

    Time Complexity: O(K * sqrt(N + M))

    Space Complexity: O(N + M + K)



    Where K is the potential pairs and N and M are the number of boys and girls respectively.

'''





# Array to store the results.

result = []



# Graph to map the boy pair with girl.

graph = []



# Utility Arrays for bfs and dfs.

pairU = []

pair = []

distanceOfU = []

qq = []



# Bfs function to find agumented path

def bfs(n):

	head = 0

	cnt = 0

	distanceOfU[0] = n

	

	for u in range(1, n + 1):

		

		if (pair[u] == 0):

			distanceOfU[u] = 0

			qq[head + cnt] = u



			cnt += 1

		else:

			distanceOfU[u] = n

			

	while (cnt > 0):

		

		u = qq[head]

		head += 1

		cnt -= 1

		d = distanceOfU[u] + 1

		

		adj = graph[u]

		

		for v in adj:

			

			w = pairU[v]

			if (distanceOfU[w] == n):

				

				distanceOfU[w] = d

				if (w == 0):

					return True

					

				qq[head + cnt] = w

				cnt += 1



	return False





# Augment current matching M with a maximal set of vertex disjoint shortest-length paths using DFS

def dfs(n, u):

	if (u == 0):

		return True

		

	d = distanceOfU[u] + 1

	adj = graph[u]



	for v in adj:

		w = pairU[v]

		if(distanceOfU[w] == d and dfs(n, w)):

			pair[u] = v

			pairU[v] = u

			return True

			

	distanceOfU[u] = n

	return False







def hopcroftKarp(n, m):



	for i in range(n + 1):

		pair.append(0)

		distanceOfU.append(0)

		qq.append(0)

	

	for i in range(m + 1):

		pairU.append(0)



	c = 0

	

	# Use BFS to build an alternating level graph, rooted at unmatched vertices in the boy set

	while (bfs(n)):

		for u in range(1, n + 1):

			if (pair[u] == 0 and dfs(n, u)):

				c += 1





# Function to clear all global variables.

def init():

        result.clear()

        graph.clear()

        pair.clear()

        pairU.clear()

        distanceOfU.clear()

        qq.clear()



def danceTogether(edges, n, m, k):



	init()



	for i in range(n + 1):

		graph.append([])



	i = 0

	# Create Graph 

	while (k > 0):

		u = edges[i][0]

		v = edges[i][1]

		graph[u].append(v)

		i += 1

		k -= 1

		

	# Hopcroft_karp algorithm 

	hopcroftKarp(n, m)



	for i in range(1, n + 1):

		if (pair[i] != 0):

			temp = []

			temp.append(i)

			temp.append(pair[i])

			result.append(temp)



	return result

/*

    Time Complexity: O(K * sqrt(N + M))

    Space Complexity: O(N + M + K)



    Where K is the potential pairs and N and M are the number of boys and girls respectively.

*/





// Array to store the results.

vector> result;



// Graph to map the boy pair with girl.

vector> graph;



// Utility Arrays for bfs and dfs.

vector pairU;

vector pairs;

vector distanceOfU;

vector qq;



// Bfs function to find agumented path

bool bfs(int n)

{

	int head = 0;

	int cnt = 0;

	distanceOfU[0] = n;

	

	for(int u = 1; u < n + 1; u++)

    {	

		if (pairs[u] == 0)

        {

			distanceOfU[u] = 0;

			qq[head + cnt] = u;

			cnt += 1;

        }

        else

        {

			distanceOfU[u] = n;

        }	

    }



	while (cnt > 0)

    {	

		int u = qq[head];

		head += 1;

		cnt -= 1;

		int d = distanceOfU[u] + 1;

		

		vector adj = graph[u];

		

		for(int i = 0; i < adj.size(); i++)

        {	

            int v = adj[i];

			int w = pairU[v];



			if (distanceOfU[w] == n)

            {	

				distanceOfU[w] = d;

				

                if (w == 0)

                {

                    return true;

                }

					

				qq[head + cnt] = w;

				cnt += 1;

            }

        }

    }



	return false;

}



// Augment current matching M with a maximal set of vertex disjoint shortest-length paths using DFS

bool dfs(int n, int u)

{

	if (u == 0)

    {

        return true;

    }

		

	int d = distanceOfU[u] + 1;

	vector adj = graph[u];



	for(int i = 0; i < adj.size(); i++)

    {    

        int v = adj[i];

		int w = pairU[v];

		

        if(distanceOfU[w] == d and dfs(n, w))

        {

			pairs[u] = v;

			pairU[v] = u;

			return true;

        }

    }

			

	distanceOfU[u] = n;

	return false;

}





void hopcroftKarp(int n, int m)

{

	for(int i = 0; i < n + 1; i++)

    {

		pairs.push_back(0);

		distanceOfU.push_back(0);

		qq.push_back(0);

    }

	

	for(int i = 0; i < m + 1; i++)

		pairU.push_back(0);



	int c = 0;

	

	// Use BFS to build an alternating level graph, rooted at unmatched vertices in the boy set

	while (bfs(n))

    {

		for(int u = 1; u < n + 1; u++)

        {

			if (pairs[u] == 0 and dfs(n, u))

            {

				c += 1;

            }

        }

    }

}





// Function to clear all global variables.

void init()

{

    result.clear();

    graph.clear();

    pairs.clear();

    pairU.clear();

    distanceOfU.clear();

    qq.clear();

}



vector> danceTogether(vector> edges, int n, int m, int k)

{

	init();



	for(int i = 0; i < n + 1; i++)

    {   

        vector temp;

		graph.push_back(temp);

    }



	int i = 0;



	// Create Graph 

	while (k > 0)

    {

		int u = edges[i][0];

		int v = edges[i][1];

		graph[u].push_back(v);

		i += 1;

		k -= 1;

    }

		

	// Hopcroft_karp algorithm 

	hopcroftKarp(n, m);



	for(i = 1; i < n + 1; i++)

    {

		if (pairs[i] != 0)

        {

			vector temp;

			temp.push_back(i);

			temp.push_back(pairs[i]);

			result.push_back(temp);

        }

    }



	return result;

}