Go Back
Aarya Celebrates Dussehra (100)
Description

Celebration of the festival of Dussehra in Bengal and eastern India is indeed unique. No other festival anywhere can match the Pooja season in grandeur, rituals, expression of family bonds and sheer size of mass participation. Our friend Aarya is also excited for Dussehra this year.

During Dussehra, all of her N family members join her. Out of these N family members only M know each other very well and they share about everything with each other. We know these N distinct family members and also about their M strong bond and relationships.

But when all of these family members come together, one of the family member S starts a rumour. This is an yearly tradition. This year, Aarya wants to find out who will be the first person and the last person of the family to know. She also knows that S only tells this rumour to his friendly family members alphabetically and once S tells his first friendly family member that friendly family member tells his immediate first friendly family member alphabetically and it goes on simultaneously like fire.(here each of the family member tells the rumour to their immediate alphabetically first friendly family member, e.g. If A has bond with X Y Z, A will first tell it to X, then Y and then Z but will spread at the same time and be counted equally. But there is also a chance that X has a bond with C and C has a bond with Y then, in this case Y will receive rumour before it comes to him/her from A and will be counted last).
Since Aarya is busy in a lot of decoration work, she needs your help.

Hint: Rumour spreads like Depth First Fire.

Input

The first line of the input is an integer T, denoting the number of test cases.
Each test case starts with two integers denoting N and M as mentioned above.
Next line contains N characters with a space between each of them denoting the family members.
Next M lines contains X and Y two characters denoting a friendship among them.
Next line contains S the character of the family member who starts the rumour.

Output

For each test case, output two characters AX and AY in a single line with a space
between them. Here AX will be the first person to know the secret (also alphabetically
too if there are multiple characters with the same time) and AY will be the last person to
know (also alphabetically last if there are multiple characters with same time).

Constraints

1 <= T <= 10.
2 <= N, M <= 26
All characters are uppercase and in range from A to Z.
X and Y will be any two characters from N given characters.

Example
Copy Input

Input:
2
4 4
A B O Z
A B
A Z
B Z
B O
O
6 7
A B C X Y Z
A Z
A X
A Y
Y C
X C
X B
B Z
X
Output:
B Z
A C

Explanation

Case 1:


Secret is shared by O to B first.
So traversal is: B->A->Z.
So B is first and Z is last.
Case 2:

Secret is shared by X to A first.
So traversal is: A->Y->C and A->Z->B.
Both Y and Z are reached at same time and B and C are reached at same time.
But alphabetically C comes next to B so C is the answer.
So A is first and C is last.

September Queue
36 hour long contest



Announcement
01:40 PM: Check your submission to see details about CE or RTE
12:28 PM: In Problem D, all the numbers are in single line for each test
Tips and Tricks for Python: Visit Here
Tips and Tricks for C++: Visit Here
Tips and Tricks for Java: Visit Here

Problem Tags
graphs,strings

Supported by our Coding Partner