SL苣的集合论

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

到了大一下学期了,SoLo苣和他的同学们一起 ,“被迫”去上离散数学的课程,众所周知,SoLo苣的课堂表现可是超级“好”的,上课“回答”问题相当积极,得到了老师的高度重视,这不,老师看他根骨奇佳,让他来计算集合的复合关系运算:

设A是一个集合,关系集合R和S是集合A上的二元关系,求R与S的复合关系R。S。

如设集合A={1,2,3,4},关系集合R={<1,2>,<3,4>,<2,2>},S= {<4,2>,<2,3>,<3,1>},则R与S的复合为R。S={<1,3>,<2,3>,<3,2>}(详见第一组示例和提示)。

开玩笑嘛,SoLo苣的心思压根不在课堂上,哪里会这个呀,在他的再三恳求下,老师同意让他找一个援兵,他毫不犹豫的选择了你,看着他楚楚可怜的模样,你一定不忍心让他失望吧,你能不能帮他解决问题呢?

Input

输入数据有多组,对于每组输入:

第一行是一个整数n,代表集合A的元素的个数,默认A中的元素为1~n,1<=n<=200;

第二行是一个整数r,代表R的关系元素的个数,1<=r<=n*n;

接下来r行,每行两个数x、y,代表R的第i个关系R[i]{<x,y>};

下一行是一个整数c,代表S的关系元素的个数,1<=c<=n*n;

接下来c行,每行两个数x、y,代表S的第i个关系S[i]{<x,y>}。

Output

对于每组样例输出其对应的R。S,每行输出一个关系x,y,中间用空格隔开,输出按照前域从小到大排列;若前域相同,则按照后域从小到大排列(详见示例)。

Sample Input

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

Sample Output

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

Hint

对于关系的复合:设A是一个集合,RS是集合A上的二元关系,则RS相同部分得整合即为RS的复合。换句话说,关系的复合是集合与集合间相同部分的统一化整合,它的定义为

所以,欲求关系的复合。只需前一个集合的后域是后一个集合的前域。

Source

不得不放弃、