离散题目16

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出集合A,以及集合A上的关系R,求关系R的自反闭包。

Input

首先输入t,表示有t组数据.    

每组数据第一行输入n,表示A中有n个数据,接下来一行输入n个数,(4 <= n < 100, 0 < Ai < 100)

第二行输入m,代表R中有m对关系(0 < m < 100)

接下来m行每行输入x,y代表< x,y >这对关系.(从小到大给出关系,如果x相同,按y排列)

Output

输出题目要求的关系集合,每行输出一对关系,输出顺序按照中的x大小非递减排列,假如x相等按照y大小非递减排列.

每组数据末尾额外输出一行空行。

Sample Input

1
5
1 2 3 4 5
6
1 1
1 2
2 3
3 3
4 5
5 1

Sample Output

1 1
1 2
2 2
2 3
3 3
4 4
4 5
5 1
5 5

Hint

Source

Johsnows