F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4982. -- 第三题

4982: 第三题

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 3  Solved: 0
[Submit][Status][Discuss]

Description

sl想打dota2了,但他现在在机房,而且yz就在他旁边,他自然不能玩dota2这种这么容易被发现(鼠标、键盘发出
啪啪啪的声音,眼睛中射出诡异的光)的游戏,所以他只好打开了一个小游戏。这个小游戏是这样的:在一个平面
上有n个A类点(从1~n编号),m个B类点(从1~m编号)。A类点很团结,他们想用n-1条边将他们连成一棵树;B
类点也想用m-1条边连成一棵树(边不可弯曲)。但这些边都不能在非AB类点出相交。如果成功连边则过关。sl有
个不好的习惯:如果没有过关,他就会气得砸键盘。如果在平时,没有什么关系(因为sl不喜欢运动,只喜欢打游
戏,以他的力气砸不坏键盘);然而此时yz在他旁边,他一砸键盘,yz就知道他在打游戏了,一定会狠狠地D他一
顿。凭sl那点可怜的智商,当然过不了关啦,所以为了拯救sl,你只好教他玩了。

Input

第一行两个整数n,m。含义如题所述。
接下来n行,每行两个整数,代表A类点的位置。
接下来m行,每行两个整数,代表B类点的位置。
n+m≤3000,坐标不超过1000000000,没有三点共线。

Output

如果无解,输出"GG!"(不含引号)。
否则输出n+m-2行。
前n-1行,每行两个整数a,b,代表在a号A类点和b号A类点间连一条边。
前m-1行,每行两个整数a,b,代表在a号B类点和b号B类点间连一条边。

Sample Input

3 2
1 0
0 1
2 3
0 0
1 1

Sample Output

1 3
2 3
1 2

HINT

请不要提交!

Source

[Submit][Status][Discuss]

HOME Back