← 返回题目列表

AtCoder · utpc2011_6

F. 生成树

中文机器翻译题面 查看原题
我们收到报告称此问题评分不正确。

现在,G○○gle Code Jam 的地区赛即将开始。 左边座位上的男生 ID 好像叫 wata。 回忆起在东京大学的日子,好像有过类似 ID 的伙伴。 但是,我的伙伴应该没有一个不是美少女。

我记忆中的 wata 喜欢马特罗伊德。 尤其喜欢马特罗伊德交叉, 对各种马特罗伊德进行交叉会感到一种兴奋,是个有些特别的人。

我记得有人说过,如果使用马特罗伊德(Matroid)的理论力量,寻找在给定图上不共享边的多个生成树是一个非常简单的问题。然而,对于特殊的图,是否存在比直接应用马特罗伊德算法更高速的算法呢?

問題

N 在拥有 个顶点的完全图中, 创建 不共享边的生成树 K 个。

完全图是指在所有不同的两个顶点之间有一条边的图。下图是一个4顶点完全图的例子。

../../assets/statements/atcoder/utpc2011_6/002-269f9ba57ca99a6bd1d3322d.webp

4顶点的完全图。

生成树是指由原图的所有顶点和部分边组成的树。树是指连通且不包含回路的图。下图是4顶点完全图中两棵不共享边的生成树。

../../assets/statements/atcoder/utpc2011_6/001-0c658475f770e6f1b67d3d8d.webp

4顶点完全图的生成树例。

../../assets/statements/atcoder/utpc2011_6/003-e5f411d39c92c8a6e7800d90.webp

是由 4 个顶点组成的完全图的生成树,并且不与之前的例子共享边。

入力

输入由一行组成, 两个整数 N, K 被写着。

出力

满足条件 K 当无法生成指定数量的生成树时,仅输出 -1。

满足条件 K 当可以生成指定数量的生成树时, K 按回车分隔输出每个生成树。 一棵生成树用 N - 1 行表示。 在 i 行中,输出该生成树的边 i 所连接的两个顶点,用空格分隔表示两个整数。 其中,顶点表示为从 1 到 1 减去 N 的整数。

制約

  • 2 ≤ N ≤ 10000
  • 1 ≤ K ≤ 100

部分点

针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。

  • 1 ≤ N ≤ 8

入出力例

入出力例 1

入力例 1:

4 2

输入示例 1 的输出示例:

1 2
1 4
2 3

1 3
2 4
3 4

此输入输出示例对应问题文中的图。

入出力例 2

入力例 2:

4 3

输入示例 2 的输出示例:

-1