Go Back

##### Aarya Celebrates Dussehra (100)

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.

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.

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.

Tips and Tricks for Python: Visit Here

Tips and Tricks for C++: Visit Here

Tips and Tricks for Java: Visit Here