Problem D
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
终于追上yangzhe1991大牛了,yangzhe1991轻抚着goagain的头笑而不语,交给了goagain一个任务,采果子... .这里有一个你可以认为是无限大的果园.当然,所有的果树都是长在整数点上.不过果园上面有一些整数点是空地,你可以在任意两个空地上连接一条通道,我们当然希望通道上面的果树尽可能的多啦.不过有一点小小的要求,你可以连的通道数量是有限的...另外,需要保证所有的空地是连通的
Input
有多组测试数据 对于每组测试数据 第一行是整数n,k 代表有n个空地,你最多能连k条通道 最多只有50个点
第2行到第n+1行每行包含2个整数 代表这个空地的横纵坐标
第2行到第n+1行每行包含2个整数 代表这个空地的横纵坐标
Output
输出给定条件下能经过最多的果树的数量,为了简便起见,如果多条通路都经过一个果树,你可以重复计算,如果通道无法连通所有的空地点,则输出-1
Sample Input
4 3 0 0 0 2 2 0 2 2 3 1 2 3 5 4 2 2
Sample Output
3 -1