Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is teaching a cooking course. There are $N$ students attending the course, numbered $1$ through $N$.

Before each lesson, Chef has to take attendance, i.e. call out the names of students one by one and mark which students are present. Each student has a first name and a last name. In order to save time, Chef wants to call out only the first names of students. However, whenever there are multiple students with the same first name, Chef has to call out the full names (both first and last names) of all these students. For each student that does not share the first name with any other student, Chef may still call out only this student's first name.

Help Chef decide, for each student, whether he will call out this student's full name or only the first name.

------  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 a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of the following $N$ lines contains two space-separated strings denoting the first and last name of student $i$.

------  Output ------
For each test case, print $N$ lines. For each valid $i$, the $i$-th of these lines should describe how Chef calls out the $i$-th student's name ― it should contain either the first name or the first and last name separated by a space.

------  Constraints  ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 100$
all first and last names contain only lowercase English letters
the lengths of all first and last names are between $1$ and $10$ inclusive

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
1

4

hasan jaddouh

farhod khakimiyon

kerim kochekov

hasan khateeb
----- Sample Output 1 ------ 
hasan jaddouh

farhod

kerim

hasan khateeb

Difficulty: EASY
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
for k in range(int(input())):
	n = int(input())
	l = []
	s = []
	for i in range(n):
		a = input()
		x = a.split(' ')
		l.append(x[0])
		s.append(x[1])
	for i in range(len(l)):
		if l.count(l[i]) >= 2:
			print(l[i], s[i])
		else:
			print(l[i])


t = int(input())
for i in range(t):
	n = int(input())
	first = []
	second = []
	for j in range(n):
		temp = input()
		x = temp.split(' ')
		first.append(x[0])
		second.append(x[1])
	for i in range(len(first)):
		if first.count(first[i]) >= 2:
			print(first[i], second[i])
		else:
			print(first[i])


t = int(input())
while t > 0:
	n = int(input())
	arr = []
	for i in range(n):
		(a, b) = input().split(' ')
		arr.append([a, b])
	for i in range(n):
		f = 0
		for j in range(n):
			if arr[i][0] == arr[j][0] and i != j:
				f = 1
				break
		if f == 1:
			print(arr[i][0], ' ', arr[i][1])
		else:
			print(arr[i][0])
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		s = input().split()
		l.append(s)
	ll = []
	for j in range(n):
		ll.append(l[j][0])
	for jj in range(n):
		c = ll.count(ll[jj])
		if c > 1:
			print(*l[jj])
		else:
			print(ll[jj])


t = int(input())
for _ in range(t):
	n = int(input())
	names = []
	surnames = []
	for i in range(n):
		(name, surname) = map(str, input().split())
		names.append(name)
		surnames.append(surname)
	for i in range(n):
		if names.count(names[i]) > 1:
			print(names[i], surnames[i])
		else:
			print(names[i])


for i in range(int(input())):
	n = int(input())
	l = []
	for j in range(n):
		l.append(input())
	d = dict()
	for k in l:
		(fi, la) = k.split()
		if fi in d.keys():
			d[fi] += 1
		else:
			d[fi] = 1
	for k in l:
		(fi, la) = k.split()
		if d.get(fi) > 1:
			print(k)
		else:
			print(fi)


for _ in range(int(input())):
	n = int(input())
	l = []
	s = []
	for i in range(n):
		s1 = input()
		l.append(s1)
		x = s1.split(' ')
		s.append(x[0])
	for i in range(len(s)):
		if s.count(s[i]) > 1:
			print(l[i])
		else:
			print(s[i])


for _ in range(int(input())):
	firstname = []
	lastname = []
	d = {}
	for x in range(int(input())):
		(f, l) = map(str, input().split())
		firstname.append(f)
		lastname.append(l)
	for name in range(len(firstname)):
		if firstname.count(firstname[name]) > 1:
			print(firstname[name], lastname[name])
		else:
			print(firstname[name])


def attendance_check(students):
	names = {}
	result = []
	for student in students:
		(first, last) = student.split()
		if first in names:
			names[first].append(last)
		else:
			names[first] = [last]
	for student in students:
		(first, last) = student.split()
		if len(names[first]) > 1:
			result.append(student)
		else:
			result.append(first)
	return result
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	students = []
	for j in range(n):
		students.append(input().strip())
	result = attendance_check(students)
	for student in result:
		print(student)


t = int(input())
for i in range(t):
	n = int(input())
	L = []
	p = []
	for j in range(n):
		v = input()
		k = v.split(' ')
		L.append(v)
		p.append(k[0])
	for j in range(len(p)):
		if p.count(p[j]) > 1:
			print(L[j])
		else:
			print(p[j])


t = int(input())
for i in range(t):
	l = []
	sn = []
	n = int(input())
	for j in range(n):
		s = input()
		s = s.split(' ')
		l.append(s[0])
		sn.append(s[1])
	for j in range(n):
		if l.count(l[j]) > 1:
			print(l[j], sn[j])
		else:
			print(l[j])


t = int(input())
for i in range(t):
	n = int(input())
	d = []
	e = []
	for i in range(n):
		(a, b) = map(str, input().split())
		d.append(a)
		e.append(b)
	for i in range(n):
		if d.count(d[i]) > 1:
			print(d[i], e[i])
		else:
			print(d[i])


try:
	for _ in range(int(input())):
		(F, L) = ([], [])
		for n in range(int(input())):
			x = input().split()
			F.append(x[0])
			L.append(x[1])
		for i in range(len(F)):
			if F.count(F[i]) == 1:
				print(F[i])
			else:
				print(F[i], L[i])
except:
	pass


t = int(input())
for _ in range(t):
	l = []
	n = int(input())
	for i in range(n):
		s = input()
		l.append(s.split())
	for i in range(n):
		flag = 0
		for j in range(n):
			if l[i][0] == l[j][0] and i != j:
				flag = 1
		if flag == 1:
			print(' '.join(l[i]))
		else:
			print(l[i][0])


for i in range(int(input())):
	n = int(input())
	l = []
	l1 = []
	for i in range(n):
		(s, s1) = map(str, input().split())
		l.append(s)
		l1.append(s1)
	for i in range(n):
		e = l.count(l[i])
		if e >= 2:
			print(l[i] + ' ' + l1[i])
		else:
			print(l[i])


for i in range(int(input())):
	(d, e) = ([], [])
	for j in range(int(input())):
		a = input().split()
		d.append(a[0])
		e.append(a[1])
	for j in range(len(d)):
		if d.count(d[j]) > 1:
			print(d[j], e[j])
		else:
			print(d[j])


for _ in range(int(input())):
	n = int(input())
	f = []
	l = []
	for i in range(n):
		(a, b) = input().split()
		f.append(a)
		l.append(b)
	for i in range(n):
		if f.count(f[i]) > 1:
			print(f[i], l[i])
		else:
			print(f[i])


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	st = []
	for s in range(n):
		st.append(tuple(input().split()))
	c = Counter([x for (x, y) in st])
	for (x, y) in st:
		if c[x] == 1:
			print(x)
		else:
			print(x, y)


def attendance(array1, array2, num):
	for i in range(num):
		if array1.count(array1[i]) <= 1:
			x = array1[i]
			print(x)
		else:
			x = array1[i]
			y = array2[i]
			print(x, y)
for _ in range(int(input())):
	array1 = []
	array2 = []
	num = int(input())
	for i in range(num):
		(string1, string2) = map(str, input().split())
		array1.append(string1)
		array2.append(string2)
	attendance(array1, array2, num)


for _ in range(int(input())):
	n = int(input())
	l2 = []
	l3 = []
	for j in range(n):
		s = input()
		l2.append(s)
		s = s.split(' ')
		l3.append(s[0])
	for j in l2:
		j = j.split(' ')
		if l3.count(j[0]) > 1:
			print(' '.join(j))
		else:
			print(j[0])


for _ in range(int(input())):
	n = int(input())
	l = []
	for __ in range(n):
		s = input().split()
		l.append(s[0])
		l.append(s[1])
	for i in range(0, 2 * n, 2):
		if l.count(l[i]) == 1:
			print(l[i])
		else:
			print(l[i], l[i + 1])


for _ in range(int(input())):
	n = int(input())
	first = []
	last = []
	for i in range(n):
		(a, b) = map(str, input().split())
		first.append(a)
		last.append(b)
	for i in range(n):
		if first.count(first[i]) > 1:
			print(first[i], '', last[i])
		else:
			print(first[i])


for i in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		b = input()
		b = b.split()
		a.append(b[0])
		a.append(b[1])
	d = {}
	for i in range(0, len(a), 2):
		if a[i] not in d.keys():
			d[a[i]] = 1
		else:
			d[a[i]] = d[a[i]] + 1
	for i in range(0, len(a), 2):
		if d[a[i]] == 1:
			print(a[i])
		else:
			print(a[i] + ' ' + a[i + 1])


t = int(input())
for tc in range(t):
	n = int(input())
	c = []
	d = []
	for j in range(n):
		(a, b) = map(str, input().split())
		c.append(a)
		d.append(b)
	for j in range(n):
		if c.count(c[j]) > 1:
			print(c[j], d[j])
		else:
			print(c[j])


t = int(input())
for _ in range(t):
	n = int(input())
	students = []
	for i in range(n):
		(first_name, last_name) = input().split()
		students.append((first_name, last_name))
	first_names = {}
	for (first_name, last_name) in students:
		if first_name in first_names:
			first_names[first_name].append(last_name)
		else:
			first_names[first_name] = [last_name]
	for (first_name, last_name) in students:
		if len(first_names[first_name]) > 1:
			print(first_name + ' ' + last_name)
		else:
			print(first_name)


b = int(input())
for i in range(b):
	n = int(input())
	u = []
	v = []
	for i in range(n):
		(a, c) = map(str, input().split())
		u.append(a)
		v.append(c)
	for i in range(n):
		if u.count(u[i]) > 1:
			print(u[i], v[i])
		else:
			print(u[i])


for t in range(int(input())):
	n = int(input())
	listname = []
	first = []
	for i in range(n):
		(f, l) = map(str, input().split(' '))
		name = f + ' ' + l
		first.append(f)
		listname.append(name)
	for j in range(n):
		if first.count(first[j]) > 1:
			print(listname[j])
		else:
			print(first[j])


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	for i in range(n):
		s = l[i]
		k = s.split(' ')
		for j in range(n):
			flag = 1
			if j != i:
				p = l[j]
				q = p.split(' ')
				if k[0] == q[0]:
					print(l[i])
					flag = 0
					break
		if flag == 1:
			print(k[0])


import copy
for i in range(int(input())):
	n = int(input())
	A = []
	B = []
	for i in range(n):
		temp = input()
		A.append(temp)
		(f1, f2) = temp.split()
		B.append(f1)
	for i in range(n):
		if B.count(B[i]) > 1:
			print(A[i])
		else:
			print(B[i])


for _ in range(int(input())):
	x = []
	y = []
	for b in range(int(input())):
		(a, c) = map(str, input().split(' '))
		x.append(a)
		y.append(c)
	for val in range(0, len(x)):
		if x.count(x[val]) > 1:
			print(x[val] + ' ' + y[val])
		else:
			print(x[val])


def check_attend(cookers):
	cooks = {}
	attend = []
	for student in cookers:
		(first, last) = student.split()
		if first in cooks:
			cooks[first].append(last)
		else:
			cooks[first] = [last]
	for student in cookers:
		(first, last) = student.split()
		if len(cooks[first]) > 1:
			attend.append(student)
		else:
			attend.append(first)
	return attend
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	cookers = []
	for j in range(n):
		cookers.append(input().strip())
	attend = check_attend(cookers)
	for student in attend:
		print(student)


t = int(input())
for i in range(t):
	n = int(input())
	j = []
	k = []
	for i in range(n):
		(a, b) = map(str, input().split())
		j.append(a)
		k.append(b)
	for i in range(n):
		if j.count(j[i]) > 1:
			print(j[i], k[i])
		else:
			print(j[i])


for i in range(int(input())):
	fname = {}
	name = []
	for j in range(int(input())):
		temp = input()
		name.append(temp)
		fn = temp.split()[0]
		ln = temp.split()[1]
		if fn not in fname.keys():
			fname[fn] = 1
		else:
			fname[fn] += 1
	for i in name:
		fn = i.split()[0]
		ln = i.split()[1]
		if fname[fn] > 1:
			print(i)
		else:
			print(fn)


n = int(input())
for i in range(n):
	li = []
	tot = int(input())
	for j in range(tot):
		name = input()
		li.append(name)
	l = li.copy()
	for k in range(tot):
		count = 0
		for m in range(tot):
			if li[m].find(li[k].split(' ')[0]) != -1:
				count += 1
		if count == 1:
			l[k] = li[k].split(' ')[0]
	for n in l:
		print(n)


for _ in range(int(input())):
	no = int(input())
	firsts = []
	names = []
	for i in range(no):
		(f, l) = map(str, input().split())
		firsts.append(f)
		names.append([f, l])
	for i in range(no):
		if firsts.count(names[i][0]) != 1:
			print(names[i][0], names[i][1])
		else:
			print(names[i][0])


t = int(input())
for k in range(t):
	n = int(input())
	students = []
	f_name = []
	f = []
	for i in range(n):
		str = input()
		l = str.split()
		for j in range(len(f_name)):
			if l[0] == f_name[j]:
				f[j] = 1
				f.append(1)
				break
		else:
			f.append(0)
		f_name.append(l[0])
		students.append(str)
	for i in range(n):
		if f[i] == 1:
			print(students[i])
		else:
			print(f_name[i])


t = int(input())
while t > 0:
	n = int(input())
	l = []
	for i in range(n):
		k = input()
		if k.find(' ') != -1:
			k = k.split(' ')
		l.append(k)
	for i in range(n):
		b = False
		for j in range(n):
			if l[i][0] == l[j][0] and i != j:
				print(l[i][0], l[i][1])
				b = True
				break
		if not b:
			print(l[i][0])
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	p = []
	q = []
	for i in range(n):
		(a, b) = map(str, input().split())
		p.append(a)
		q.append(b)
	for i in range(n):
		if p.count(p[i]) > 1:
			print(p[i], q[i])
		else:
			print(p[i])


t = int(input())
for i in range(t):
	n = int(input())
	name = []
	s_name = []
	for i in range(n):
		(fn, ln) = map(str, input().split())
		name.append(fn)
		s_name.append(ln)
	for i in range(n):
		if name.count(name[i]) == 1:
			print(name[i])
		else:
			print(name[i], s_name[i])


def main():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		names = []
		for i in range(n):
			(first, last) = input().strip().split()
			names.append((first, last))
		first_names = [first for (first, last) in names]
		unique_names = set(first_names)
		for (first, last) in names:
			if first_names.count(first) > 1:
				print(first, last)
			else:
				print(first)
main()


for i in range(int(input())):
	n = int(input())
	(l1, l2) = ([], [])
	for i in range(n):
		a = list(map(str, input().split()))
		l1.append(a[0])
		l2.append(a[1])
	for i in range(len(l1)):
		if l1.count(l1[i]) > 1:
			print(l1[i] + ' ' + l2[i])
		else:
			print(l1[i])


t = int(input(''))
for x in range(t):
	n = int(input(''))
	first = []
	last = []
	for y in range(n):
		(name, surname) = input('').split()
		first.append(name)
		last.append(surname)
	for y in range(len(first)):
		if first.count(first[y]) > 1:
			print(first[y], last[y])
		else:
			print(first[y])


t = int(input())
for i in range(t):
	n = int(input())
	f = []
	l = []
	for j in range(n):
		(x, y) = map(str, input().split())
		f.append(x)
		l.append(y)
	for j in range(n):
		if f.count(f[j]) > 1:
			print(f[j], l[j])
		else:
			print(f[j])


for i in range(int(input())):
	n = int(input())
	(first, last) = ([], [])
	for i in range(n):
		(f, l) = map(str, input().split())
		first.append(f)
		last.append(l)
	for i in range(n):
		if first.count(first[i]) > 1:
			print(first[i], last[i])
		else:
			print(first[i])


for _ in range(int(input())):
	n = int(input())
	fn = []
	ln = []
	for i in range(n):
		(x, y) = map(str, input().split())
		fn.append(x)
		ln.append(y)
	for i in range(n):
		if fn.count(fn[i]) > 1:
			print(fn[i], ln[i])
		else:
			print(fn[i])


a = int(input())
while a > 0:
	c = int(input())
	l = []
	for i in range(c):
		l.append(input().split())
	for i in range(c):
		k = l[i][0]
		c1 = 0
		for j in range(c):
			if k == l[j][0]:
				c1 += 1
		if c1 > 1:
			print(l[i][0], end=' ')
			print(l[i][1])
		else:
			print(l[i][0])
	a -= 1


T = int(input())
for i in range(T):
	N = int(input())
	l = []
	m = []
	for i in range(N):
		(i, j) = map(str, input().split())
		l.append(i)
		m.append(j)
	for i in range(N):
		if l.count(l[i]) > 1:
			print(l[i], m[i])
		else:
			print(l[i])


for i in range(int(input())):
	n = int(input())
	(l, l1, l2) = ([], [], [])
	for j in range(n):
		(fi, la) = input().split()
		l.append(fi)
		l1.append(fi + ' ' + la)
	s = set(l)
	for x in s:
		if l.count(x) > 1:
			l2.append(x)
	for j in range(len(l)):
		if l[j] in l2:
			print(l1[j])
		else:
			print(l[j])


T = int(input())
for tcase in range(T):
	n = int(input())
	l = []
	m = []
	for n in range(1, n + 1):
		s = input()
		l.append(s)
	for i in l:
		i = i.split(' ')
		m.append(i[0])
	for j in range(len(m)):
		if m.count(m[j]) == 1:
			print(m[j])
		else:
			print(l[j])


t = int(input())
for m in range(t):
	n = int(input())
	l = []
	m = []
	while n:
		s = input()
		l.append(s)
		n = n - 1
	for i in l:
		i = i.split(' ')
		m.append(i[0])
	for j in range(len(m)):
		if m.count(m[j]) == 1:
			print(m[j])
		else:
			print(l[j])


t = int(input())
while t != 0:
	n = int(input())
	k = ''
	while n != 0:
		s = input()
		k += s
		k += ' '
		n -= 1
	k = k.split(' ')
	for i in range(0, len(k) - 1, 2):
		l = k.count(k[i])
		if l == 1:
			print(k[i])
		else:
			print(k[i], k[i + 1])
	t -= 1


T = int(input())
for _ in range(T):
	first_name = set()
	duplicate_name = set()
	name = []
	n = int(input())
	for _ in range(n):
		(a, b) = input().split()
		name.append([a, b])
		if a in first_name:
			duplicate_name.add(a)
		else:
			first_name.add(a)
	for i in name:
		if i[0] in duplicate_name:
			print(i[0], i[1])
		else:
			print(i[0])


for _ in range(int(input())):
	first_name_set = set()
	duplicate_name = set()
	name = []
	for __ in range(int(input())):
		(a, b) = input().split()
		name.append([a, b])
		if a in first_name_set:
			duplicate_name.add(a)
		else:
			first_name_set.add(a)
	for i in name:
		if i[0] in duplicate_name:
			print(i[0], i[1])
		else:
			print(i[0])


T = int(input())
while T:
	N = int(input())
	first_name = []
	last_name = []
	indexes_of_same_names = []
	for i in range(N):
		(F, L) = input().split()
		first_name.append(F)
		last_name.append(L)
	for i in range(N - 1):
		for j in range(i + 1, N):
			if first_name[i] == first_name[j]:
				if i in indexes_of_same_names and j not in indexes_of_same_names:
					indexes_of_same_names.append(j)
				elif i in indexes_of_same_names and j in indexes_of_same_names:
					continue
				else:
					indexes_of_same_names.append(i)
					indexes_of_same_names.append(j)
	for i in range(N):
		if i in indexes_of_same_names:
			print(first_name[i] + ' ' + last_name[i])
		else:
			print(first_name[i])
	T -= 1