There are total n tasks given to a group of 5 students in a class. Three of those five students completed m tasks of their choices and left the group. Now the burden of completing remaining tasks is on the two students Tanya and Manya. Suppose the n tasks are in an array form 1,2,3,...n. Tanya and Manya decided to complete their remaining tasks in the following manner :- First of the remaining task is done by Tanya and the next remaining one by Manya . For example if n = 10 and m = 4 and the completed 4 tasks are {2, 3, 5, 7} then the reamining tasks are {1, 4, 6, 8, 9, 10} so, Tanya completes {1, 6, 9} tasks and Manya completes {4, 8, 10} tasks and thereby completing the n tasks given.
Given n, m and the indexes (1 for first task, 2 for second task and so on..) of completed tasks, find the tasks which Tanya and Manya have to complete.
Example 1:
Input:
n = 15, m = 6
arr[] = {2, 5, 6, 7, 9, 4}
Output: 
1 8 11 13 15 
3 10 12 14 
Explanation: The remaining tasks are :
{1, 3, 8, 10, 11, 12, 13, 14, 15}.
So Tanya should take these tasks :
{1, 8, 11, 13, 15}.
And Manya should take these tasks :
{3, 10, 12, 14}.
Example 2:
Input:
n = 4, m = 3
arr[] = {2, 4, 3}
Output: 
1
Explanation: There are no task for Manya.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findTasks() which takes the array of integers arr, m and n as parameters and returns a pair of an array of integers denoting the answer.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ m ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ n

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3


# return [[tanya's tasks], [manya's tasks]]
class Solution:
    def solve(self, arr, n, m):
        # code here

Solutions:
class Solution:

	def solve(self, arr, n, m):
		lis = [1] * (n + 1)
		for i in arr:
			lis[i] = 0
		t = True
		tlis = []
		m = False
		mlis = []
		for i in range(1, n + 1):
			if lis[i]:
				if t:
					t = False
					m = True
					tlis.append(i)
				else:
					m = False
					t = True
					mlis.append(i)
		return (tlis, mlis)


class Solution:

	def solve(self, arr, n, m):
		a = [i for i in range(1, n + 1)]
		b = list(set(a) ^ set(arr))
		c = b[::2]
		d = b[1::2]
		return [c, d]


class Solution:

	def solve(self, arr, n, m):
		setti = set(arr)
		result = [i for i in range(1, n + 1) if i not in setti]
		return [result[::2], result[1::2]]


class Solution:

	def solve(self, arr, n, m):
		tanya = []
		arr = set(arr)
		manya = []
		flag = True
		for ele in range(1, n + 1):
			if ele not in arr:
				if flag:
					tanya.append(ele)
				else:
					manya.append(ele)
				flag = not flag
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		dict1 = {}
		dict2 = {}
		result = []
		for i in range(1, n + 1):
			dict1[i] = dict1.get(1, 0) + 1
		for i in range(len(arr)):
			dict2[arr[i]] = dict2.get(arr[i], 0) + 1
		for key in dict1:
			if key not in dict2:
				result.append(key)
		list1 = []
		for i in range(0, len(result), 2):
			list1.append(result[i])
		list2 = []
		for i in range(1, len(result), 2):
			list2.append(result[i])
		new_result = []
		new_result.append(list1)
		new_result.append(list2)
		return new_result


class Solution:

	def solve(self, arr, n, m):
		(tanya, manya, flag) = ([], [], 0)
		arr = set(arr)
		for i in range(1, n + 1):
			if i not in arr and flag == 0:
				tanya.append(i)
				flag = 1
			elif i not in arr:
				manya.append(i)
				flag = 0
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		t = []
		m = []
		s = set(arr)
		j = 1
		for i in range(1, n + 1, 1):
			if i in s:
				continue
			elif j % 2 != 0:
				t.append(i)
				j += 1
			else:
				m.append(i)
				j += 1
		l = []
		l.append(t)
		l.append(m)
		return l


class Solution:

	def solve(self, arr, n, m):
		p = [1] * n
		for i in range(m):
			p[arr[i] - 1] = 0
		l = []
		for i in range(n):
			if p[i] != 0:
				l.append(i + 1)
		k = []
		s = []
		for i in range(len(l)):
			if i % 2 == 0:
				k.append(l[i])
			else:
				s.append(l[i])
		return [k, s]


class Solution:

	def solve(self, arr, n, m):
		allVal = [0] * n
		for x in range(m):
			allVal[arr[x] - 1] = -1
		remain = []
		for x in range(n):
			if allVal[x] != -1:
				remain.append(x + 1)
		rl = len(remain)
		Tanya = []
		Manya = []
		for x in range(1, rl + 1):
			if x % 2 != 0:
				Tanya.append(remain[x - 1])
			else:
				Manya.append(remain[x - 1])
		return [Tanya, Manya]


class Solution:

	def solve(self, arr, n, m):
		p = [1] * n
		for i in range(m):
			p[arr[i] - 1] = 0
		l = []
		for i in range(n):
			if p[i] != 0:
				l.append(i + 1)
		k = []
		s = []
		for i in range(len(l)):
			if i % 2 == 0:
				k.append(l[i])
			else:
				s.append(l[i])
		return [k, s]
		remain = [x for x in range(1, n + 1) if x not in arr]
		rl = len(remain)
		Tanya = []
		Manya = []
		for x in range(1, rl + 1):
			if x % 2 != 0:
				Tanya.append(remain[x - 1])
			else:
				Manya.append(remain[x - 1])
		return [Tanya, Manya]


class Solution:

	def solve(self, arr, n, m):
		s = {int(i) for i in range(1, n + 1)}
		arr = set(arr)
		s = s - arr
		ans = [[], []]
		s = list(s)
		s.sort()
		for i in range(len(s)):
			if i % 2 == 0:
				ans[0].append(s[i])
			else:
				ans[1].append(s[i])
		return ans


class Solution:

	def solve(self, arr, n, m):
		d = {}
		for i in arr:
			d[i] = 1
		x = [i for i in range(1, n + 1) if i not in d]
		tanya = []
		manya = []
		for i in range(len(x)):
			if i % 2 == 0:
				tanya.append(x[i])
			else:
				manya.append(x[i])
		return (tanya, manya)


class Solution:

	def solve(self, arr, n, m):
		total_task = [1] * n
		for i in range(m):
			total_task[arr[i] - 1] = 0
		rem_task = []
		for i in range(n):
			if total_task[i] != 0:
				rem_task.append(i + 1)
		tanya = []
		manya = []
		for i in range(len(rem_task)):
			if i % 2 == 0:
				tanya.append(rem_task[i])
			else:
				manya.append(rem_task[i])
		return (tanya, manya)


class Solution:

	def solve(self, arr, n, m):
		rem = [None] * (n + 1)
		tanya = []
		manya = []
		flag = False
		for i in arr:
			rem[i] = 1
		for i in range(1, n + 1):
			if rem[i] != None:
				continue
			elif flag == False and rem[i] == None:
				tanya.append(i)
				flag = True
			elif flag == True and rem[i] == None:
				manya.append(i)
				flag = False
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		ht = {}
		for i in arr:
			ht[i] = 1
		tanya = []
		manya = []
		t = 1
		m = 0
		for i in range(1, n + 1):
			if i not in ht:
				if t == 1:
					tanya.append(i)
					t = 0
					m = 1
				elif m == 1:
					manya.append(i)
					t = 1
					m = 0
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		arr = list(set(arr))
		arr.sort()
		l1 = []
		l2 = []
		l = list(range(1, n + 1))
		l = list(set(l) - set(arr))
		l.sort()
		for i in range(0, len(l), 2):
			l1.append(l[i])
		for i in range(1, len(l), 2):
			l2.append(l[i])
		l3 = [l1, l2]
		return l3


class Solution:

	def solve(self, arr, n, m):
		k = {}
		for x in arr:
			if x not in k.keys():
				k[x] = 1
		ls = []
		for i in range(1, n + 1):
			if i not in k.keys():
				ls.append(i)
		m = []
		t = []
		for i in range(len(ls)):
			if i % 2 == 0:
				t.append(ls[i])
			else:
				m.append(ls[i])
		return [t, m]


class Solution:

	def solve(self, arr, n, m):
		k = [1] * n
		x = []
		y = []
		l = []
		c = 0
		for i in range(m):
			k[arr[i] - 1] = 0
		for i in range(n):
			if k[i] != 0:
				l.append(i + 1)
		for (i, j) in enumerate(l):
			if i % 2 == 0:
				x.append(j)
			else:
				y.append(j)
		return [x, y]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ans = Solution().solve(arr, n, m)
		for x in ans[0]:
			print(x, end=' ')
		print()
		for x in ans[1]:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def solve(self, arr, n, m):
		p = [1] * n
		for i in range(m):
			p[arr[i] - 1] = 0
		l = []
		for i in range(n):
			if p[i] != 0:
				l.append(i + 1)
		k = []
		s = []
		for i in range(len(l)):
			if i % 2 == 0:
				k.append(l[i])
			else:
				s.append(l[i])
		return [k, s]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ans = Solution().solve(arr, n, m)
		for x in ans[0]:
			print(x, end=' ')
		print()
		for x in ans[1]:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def solve(self, arr, n, m):
		l1 = []
		l2 = []
		p = [1] * n
		a = []
		for i in range(m):
			p[arr[i] - 1] = 0
		for i in range(n):
			if p[i] != 0:
				a.append(i + 1)
		for i in range(0, len(a)):
			if i % 2 == 0:
				l1.append(a[i])
			else:
				l2.append(a[i])
		return [l1, l2]


class Solution:

	def solve(self, arr, n, m):
		s = {}
		k = []
		p = []
		s = set(s)
		for i in range(1, n + 1):
			s.add(i)
		for i in range(0, m):
			s.discard(arr[i])
		s = list(s)
		c = 0
		for i in range(len(s)):
			if i % 2 == 0:
				k.append(s[i])
			else:
				p.append(s[i])
		return [k, p]


class Solution:

	def solve(self, arr, n, m):
		res1 = []
		res2 = []
		res = []
		arr1 = []
		p = 0
		d = {}
		for i in range(0, m):
			d[arr[i]] = i
		q = 0
		for i in range(1, n + 1):
			try:
				q = d[i]
			except:
				arr1.append(i)
				p += 1
		for i in range(0, p):
			if i % 2 == 0:
				res1.append(arr1[i])
			else:
				res2.append(arr1[i])
		res.append(res1)
		res.append(res2)
		return res


class Solution:

	def solve(self, arr, n, m):
		dum = [1] * n
		for i in range(m):
			dum[arr[i] - 1] = 0
		sol = []
		for i in range(n):
			if dum[i] != 0:
				sol.append(i + 1)
		tanya = []
		manya = []
		for i in range(len(sol)):
			if i % 2 == 0:
				tanya.append(sol[i])
			else:
				manya.append(sol[i])
		return (tanya, manya)


class Solution:

	def solve(self, arr, n, m):
		a = []
		gg = {}
		for i in arr:
			if i not in gg:
				gg[i] = 1
		for i in range(1, n + 1):
			if i not in gg:
				a.append(i)
		a1 = []
		a2 = []
		for i in range(0, len(a), 2):
			k = a[i]
			a1.append(a[i])
			if i + 1 < len(a):
				a2.append(a[i + 1])
		return [a1, a2]


class Solution:

	def solve(self, arr, n, m):
		arr = set(arr)
		tanya = []
		manya = []
		turn = 't'
		for i in range(1, n + 1):
			if i not in arr:
				if turn == 't':
					tanya.append(i)
					turn = 'm'
				else:
					manya.append(i)
					turn = 't'
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		a = [i for i in range(1, n + 1)]
		b = list(set(a) ^ set(arr))
		b.sort()
		tanya = [b[i] for i in range(0, len(b), 2)]
		manya = list(set(b) ^ set(tanya))
		manya.sort()
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		tanya = []
		manya = []
		s = set()
		for val in arr:
			s.add(val)
		flag = False
		for i in range(1, n + 1):
			if i not in s:
				if not flag:
					tanya.append(i)
					flag = True
				else:
					manya.append(i)
					flag = False
		return [tanya, manya]


class Solution:

	def solve(self, arr, n, m):
		z = []
		tanya = []
		manya = []
		count1 = 0
		for i in range(1, n + 1):
			z.append(i)
		a = set(arr)
		z1 = set(z)
		ans = sorted(z1 ^ a)
		for i in range(len(ans)):
			if i % 2 == 0:
				tanya.append(ans[i])
			else:
				manya.append(ans[i])
		res = []
		res.append(tanya)
		res.append(manya)
		return res


class Solution:

	def solve(self, arr, n, m):
		l = [False] * n
		res = []
		for i in arr:
			l[i - 1] = True
		for i in range(n):
			if not l[i]:
				res.append(i + 1)
		return (res[::2], res[1::2])


class Solution:

	def solve(self, arr, n, m):
		arr = list(set(arr))
		arr.sort()
		ans = [[], []]
		c = 1
		p = 0
		i = 0
		while c <= n:
			if p < len(arr) and c == arr[p]:
				p += 1
			else:
				ans[i].append(c)
				i = (i + 1) % 2
			c += 1
		return ans


class Solution:

	def solve(self, arr, n, m):
		z = 1
		s = set(arr)
		a = []
		b = []
		for i in range(1, n + 1):
			if i in s:
				continue
			elif z % 2 != 0:
				a.append(i)
				z += 1
			else:
				b.append(i)
				z += 1
		return (a, b)


class Solution:

	def solve(self, arr, n, m):
		a = [1] * n
		for i in range(0, m):
			a[arr[i] - 1] = 0
		tasks = []
		for i in range(0, n):
			if a[i] != 0:
				tasks.append(i + 1)
		if len(tasks) == 1:
			return ([tasks[0]], [])
		t = []
		m = []
		for i in range(0, len(tasks)):
			if i % 2 == 0:
				t.append(tasks[i])
			else:
				m.append(tasks[i])
		return (t, m)


class Solution:

	def solve(self, arr, n, m):
		ma = {}
		for i in range(1, n + 1):
			ma[i] = 0
		for i in range(m):
			ma[arr[i]] = 1
		l = [i for i in range(1, n + 1) if ma[i] != 1]
		return (l[::2], l[1::2])


class Solution:

	def solve(self, arr, n, m):
		arr = sorted(set(arr))
		if n == len(arr):
			return ([], [])
		if n < m:
			return [1]
		tanya = []
		manya = []
		first = 0
		t = 0
		m = 0
		for i in range(1, n + 1):
			if first < len(arr) and arr[first] == i:
				first += 1
				continue
			elif t == 0:
				t = 1
				m = 0
				tanya.append(i)
			elif m == 0:
				m = 1
				t = 0
				manya.append(i)
		return (tanya, manya)


class Solution:

	def solve(self, arr, n, m):
		a = [0] * n
		for i in range(n):
			a[i] = i + 1
		for i in range(m):
			a[arr[i] - 1] = 0
		a = [x for x in a if x != 0]
		n = len(a)
		if n % 2 == 1:
			k = [0] * (n // 2 + 1)
			l = [0] * (n // 2)
		else:
			k = [0] * (n // 2)
			l = [0] * (n // 2)
		c = 0
		d = 0
		i = 0
		while i < n - 1:
			k[c] = a[i]
			l[d] = a[i + 1]
			c += 1
			d += 1
			i += 2
		if n % 2 == 1:
			k[n // 2] = a[n - 1]
		return (k, l)


class Solution:

	def solve(self, arr, n, m):
		s = set(arr)
		ans = {0: [], 1: []}
		tanu = True
		for i in range(1, n + 1):
			if i not in s:
				if tanu:
					ans[0].append(i)
				else:
					ans[1].append(i)
				tanu = not tanu
		return ans


from collections import Counter

class Solution:

	def solve(self, arr, n, m):
		T = []
		M = []
		count = Counter(arr)
		c = 1
		for i in range(1, n + 1):
			if i not in count:
				if c == 1:
					T.append(i)
					c = 1 - c
				else:
					M.append(i)
					c = 1 - c
		return [T, M]