You WILL Like Graph Construction

問題文

あなたの今日のラッキーアルゴリズムはグラフアルゴリズムです。最短経路と最小カットに関係するこの構築問題を解けば、きっと幸運が舞い込むことでしょう。

各頂点に $1$ から $N$ までの番号が付けられた、$N$ 頂点の重みなし単純連結無向グラフ $G$ を考えます。

$G$ に対し、$G$ と同じ頂点集合を持つ完全無向グラフ $H$ を次のように定めます。

• 各頂点対 $(u,v) ~ (1 \le u < v \le N)$ について、$H$ の頂点 $u$ と頂点 $v$ を結ぶ辺の容量を、$G$ における頂点 $u$ と頂点 $v$ の間の最短距離とする。

$H$ における頂点 $1$ と頂点 $N$ を分離する最小カットの容量が $K$ となるような $G$ が存在するか判定し、存在する場合は $1$ つ構築してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le K \le N^2$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

各テストケースについての答えを、番号順に改行区切りで出力せよ。

各テストケースについて、条件を満たす $G$ が存在しない場合、 -1 とのみ出力せよ。
存在する場合、この $G$ を以下の形式で出力せよ。

この出力は、$G$ 上に $M$ 本の辺があり、 $i ~ (1 \le i \le M)$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいることを表す。

答えが複数ある場合、そのいずれを出力しても正解と判定される。

サンプル 1

入力

2
4 4
10 100

出力

3
1 4
4 2
1 3
-1

$1$ 番目のテストケースについて、以下のように $G$ を構築することで、 $H$ の最小カットの容量を $4$ にすることができます。

$2$ 番目のテストケースについて、このような $G$ は存在しません。