問題文

頂点数が $2\times 10^5$ 以下の木であって、各頂点が茶色または緑色であり、以下の条件をすべて満たすようなものをよい枝と呼ぶことにします。

• 茶色の頂点が存在する。
• 緑色の頂点が存在する。
• 茶色の頂点に隣接する茶色の頂点の数は高々 $2$ つ。
• 茶色の頂点どうしを結ぶパスに緑色の頂点は存在しない。

また、よい枝の美しさを以下のように求めます。

• 茶色の頂点全てに対して、隣接する緑色の頂点の数を求める。
• その総積を美しさとする。

美しさがちょうど $X$ になるようなよい枝のうち、頂点数が最小のものを出力してください。そのようなものが複数ある場合は、どれを出力しても構いません。

ただし、よい枝であって条件を満たすものが存在しない場合、代わりにそのことを報告してください。特に、頂点数が $\mathbf{2\times 10^5}$ より大きい木はよい枝の条件を満たさないことに注意してください。

制約

• $1\leq X\leq 10^{18}$
• $X$ は整数

入力

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

$X$

出力

よい枝であって条件を満たすものが存在しない場合、-1とだけ出力してください。

そうでない場合、すなわち答えが存在する場合は以下のように出力してください。

$n$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{n-1}\ v_{n-1}$
$c_1\ c_2\dots c_n$

ただし、$n$ は頂点数です。あなたは頂点に $1,2,\dots,n$ と番号のついた木を出力することになります。

$u_i\ v_i$ は頂点 $u_i$ と頂点 $v_i$ を結ぶ辺、$c_i$ は頂点 $i$ の色を指します。ここで、$c_i$ は b か g である必要があり、$c_i=$ b であれば頂点 $i$ が茶色であることを、$c_i=$ g であれば頂点 $i$ が緑色であることを表します。

出力がこのフォーマットに従わなかった場合、判定結果は不定です。特に、余計な改行や空白が存在したり、必要な改行や空白が存在しない場合、WA と判定される可能性があります。

サンプル

サンプル1

入力サンプルをコピー

入力

1

出力

2
1 2
b g

この出力は以下のような木です。ただし、頂点 $1$ が茶色に、頂点 $2$ が緑色に塗られています。

この木はよい枝の条件をすべて満たしていることが確認できます。頂点 $1$ に隣接する緑色の頂点は $1$ つなので、美しさは $1$ です。頂点数が $1$ 以下の木で条件を満たすものは存在しないので、これは正しい解です。

たとえば以下のような出力は、美しさは $1$ ですが頂点数が最小でないので不正解と判定されます。

3
1 2
2 3
b g g

サンプル2

入力サンプルをコピー

入力

10

出力

9
1 2
2 3
4 2
5 4
7 4
4 6
9 4
4 8
g b g b g g g g g

この出力は以下のような木です。ただし、頂点 $2,4$ が茶色に、それ以外が緑色に塗られています。

この木はよい枝の条件をすべて満たしていることが確認できます。頂点 $2$ に隣接する緑色の頂点は $2$ つ、頂点 $4$ に隣接する緑色の頂点は $5$ つなので、美しさは $10$ です。頂点数が $8$ 以下の木で条件を満たすものは存在しないので、これは正しい解です。

998244353

-1