問題 F : 全域木

今，G○○gle Code Jam の地区大会が始まろうとしている． 左の席に座っている男の ID は wata と言うらしい． 東京大学時代の記憶に，似たような ID の仲間が居た覚えがある． しかし，僕の仲間は一人残さず美少女だったはずだ．

僕の記憶の中の wata は，マトロイドが好きだった． 特に，マトロイド交差が大好きで， 様々なマトロイド達を交差させることに一種の興奮すら覚えると言う少し変わった奴だった．

マトロイドの理論の力を使えば， 与えられたグラフ上で辺を共有しない複数の全域木を求めることはとても簡単な問題だと言っていた気がする． しかし，特別なグラフに関しては， マトロイドのアルゴリズムを直接に適用するよりも高速なアルゴリズムがあるのではないか？

問題

N 個の頂点からなる完全グラフにおいて， 辺を共有しない全域木を K 個作成せよ．

完全グラフとは，全ての相異なる 2 頂点間に 1 本の辺を持つグラフである． 下図は，4 頂点の完全グラフの例である．

../images/spanning_fig1.png

4 頂点の完全グラフ．

全域木とは，元のグラフの全ての頂点と一部の辺からなる木のことである． 木とは，連結かつ閉路を持たないグラフのことである． 下図は，4 頂点の完全グラフにおける，辺を共有しない 2 つの全域木である．

../images/spanning_fig2.png

4 頂点の完全グラフの全域木の例．

../images/spanning_fig3.png

4 頂点の完全グラフの全域木であり，前の例と辺を共有しないもの．

入力

入力は 1 行からなり， 2 つの整数 N, K が書かれている．

出力

条件を満たす K 個の全域木を作ることができない時，-1 とだけ出力せよ．

条件を満たす K 個の全域木を作ることができる時， K 個の全域木を改行で区切り出力せよ． 1 つの全域木は N - 1 行で表される． その i 行目には，その全域木の辺 i が結ぶ 2 つの頂点を表す 2 つの整数をスペースで区切り出力する． ここで，頂点は 1 から N までの整数で表すものとする．

制約

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下を満たす．

入出力例

入出力例 1

入力例 1:

4 2

入力例 1 に対する出力の例:

1 2
1 4
2 3

1 3
2 4
3 4

この入出力例は問題文中の図と対応している．

入出力例 2

入力例 2:

4 3

入力例 2 に対する出力の例:

-1
Problemsetter: 秋葉 拓哉