我们收到报告称此问题评分不正确。
现在,G○○gle Code Jam 的地区赛即将开始。 左边座位上的男生 ID 好像叫 wata。 回忆起在东京大学的日子,好像有过类似 ID 的伙伴。 但是,我的伙伴应该没有一个不是美少女。
我记忆中的 wata 喜欢马特罗伊德。 尤其喜欢马特罗伊德交叉, 对各种马特罗伊德进行交叉会感到一种兴奋,是个有些特别的人。
我记得有人说过,如果使用马特罗伊德(Matroid)的理论力量,寻找在给定图上不共享边的多个生成树是一个非常简单的问题。然而,对于特殊的图,是否存在比直接应用马特罗伊德算法更高速的算法呢?
問題
N 在拥有 个顶点的完全图中, 创建 不共享边的生成树 K 个。
完全图是指在所有不同的两个顶点之间有一条边的图。下图是一个4顶点完全图的例子。
4顶点的完全图。
生成树是指由原图的所有顶点和部分边组成的树。树是指连通且不包含回路的图。下图是4顶点完全图中两棵不共享边的生成树。
4顶点完全图的生成树例。
是由 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