Obsessive Behavior
Time Limit: 5 Seconds Memory Limit: 131072 KB
Special Judge
Bahman is a disciplined person when it comes to decisions. Even decisions like making new friends! At school, he
always made a list of people, whom he found cool, according to how much he liked them. He has his lists for
primary school (“Dabestaan” in Persian), secondary school (“Raahnamaaei” in Persian) and high school
(“Dabirestaan” in Persian) now.
Bahman is going to enter university, but he wants to make the decision of choosing a university based on his
friends.
Specifically, he knows that if he liked his friend X more than Y in one of his lists (X comes before Y in the list),
then he would like X more than Y in university (if they all go to the same university).
Unfortunately, Bahman’s friends have chosen their universities and Bahman knows this. So he wants to choose a
university where he can get the longest list of friends in the same order he made his previous lists. This list should
only contain the friends that went to the same school with Bahman from primary school to high
school.
As you might have noticed, despite the confusion, it is not odd to have friends with the same name. So you can
safely assume that if Bahman had a friend called X who is going to university U in both primary school and high
school, they are the same person.
Given Bahman’s three lists and his friends’ chosen universities, help him find the best university and the list of his
old friends there.
Dont worry! He would definitely go to a university!
Input
The input contains several test cases.
In the first line of input comes T (0 < T < 100), the number of test cases.
Each test case has 9 lines which describe 3 lists (3 lines for each list) in the order of primary school, secondary
school and high school.
The first line for each list would be n (1 ≤ n ≤ 300), the number of friends in that list. The second line contains n
case sensitive strings, each of which is at most 100-English-alphabet-characters long. The ith string is the name of
the ith person on the list. The third line contains n integers between 1 and 10 inclusive. The ith integer is the
chosen university by the ith person.
Output
For each test case, print two lines. The first line should contain the number of the university Bahman should
choose, and the second line should contain the names of friends in the correct order, separated with a
space.
If there exists more than one possible answer, print any of them.
If the list is empty, print a blank line.
Sample Input
3 4 A A A A 1 2 2 1 4 A A A A 2 1 2 1 4 A A A A 1 2 1 2 3 A B C 1 2 3 3 B C A 1 2 3 3 C A B 1 2 3 9 Mohsen Aryaz Ali Pejman Mohammad Mohammad Ali Sina Mohammad 2 2 1 2 2 1 1 3 2 8 Mohsen Ali Pejman Aryaz Mohammad Mohammad Hassan Mohammad 2 1 2 2 2 1 4 2 9 Mohsen Hassan Ali Sina Pejman Mohammad Sina Aryaz Mohammad 2 4 1 3 2 2 1 2 2
Sample Output
2 A A 1 2 Mohsen Pejman Mohammad MohammadSubmit
Source: 12th Iran Nationwide Internet Contest - Final