408140: GYM102994 E Road Construction

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Road Constructiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$n+m$$$ towns in Kingdom of Coffee Chicken, which can be seen as $$$n+m$$$ integers coordinates $$$(x_i,y_i)$$$ on the 2-dimensional plane. $$$n$$$ of them belong to Acesrc while the other $$$m$$$ towns belong to Roundgod.

Now both Acesrc and Roundgod want to build straight roads among their towns and they all want their towns are connected, which means there is a path between any two of towns. It is obvious that we need only $$$n+m-2$$$ roads to make it possible. Moreover, Acesrc and Roundgod hope that among these $$$n+m-2$$$ roads, there is no intersection other than the position of towns.

Now we hope you to provide us a construction plan.

Input

The first line contains two integers $$$n,m(n>1,m>1,n+m \leq 3000)$$$.

The following $$$n$$$ lines describe Acesrc's towns and each line contains two integers $$$x,y(0 \leq x,y \leq 10^9)$$$ representing coordinates. Their number is $$$1-n$$$ respectively.

The following $$$n$$$ lines describe Roundgod's towns and each line contains two integers $$$x,y(0 \leq x,y \leq 10^9)$$$ representing coordinates. Their number is $$$1-m$$$ respectively.

There is no repeated coordinates among those $$$n+m$$$ towns. We also guarantee that no three towns are on the same straight line among them.

Output

Please output $$$n+m-2$$$ lines in total, the first $$$n-1$$$ lines representing the construction plan of Acesrc's towns and the other $$$m-1$$$ lines representing the construction plan of Roundgod's towns. For each line of a construction plan, please output two integers $$$x,y$$$, indicating a straight road connected town $$$x$$$ and $$$y$$$.

If it is impossible to find any valid construction plan, output Impossible instead.

ExampleInput
2 3
0 0
1 1
1 0
0 1
2 3
Output
2 1
1 3
3 2

加入题单

上一题 下一题 算法标签: