A 国と B 国は仲が悪い国です。A 国は B 国を侵略するため、その鉄道網を調べようとしています。何度もスパイを送りましたが、有用な情報を得る前に必ず捕まったため、知っているのは次のことだけです。

• B 国の鉄道網には $N$ 個の駅があり、$1$ から $N$ まで番号が付いています。

• 異なる任意の二駅は、線路で直接つながっているか、線路でつながったほかの駅を経由してつながっています。

• 任意の二駅を結ぶ経路はちょうど一つです。

• 駅とその駅自身を直接結ぶ線路はありません。

スパイを送る方法の限界を悟った A 国は、B 国の鉄道会社の幹部を買収して鉄道網の図を入手しようとしています。そのまま送ると裏切り者の身元が分かるため、裏切り者は次のように図を変更してから送ります。

• 図に偽の線路を $K$ 本描きます。具体的には、図で線路によって直接つながっていない異なる駅 $a$ と $b$ を選び、偽の線路で直接結びます。これを $K$ 回繰り返します。

• 一つの駅に特別な印を付けます。

• 最後に、すべての駅番号を消します。

裏切り者は完成した図を A 国に送ります。この情報だけでは B 国の鉄道網の図だと分かりにくいため、秘密情報が漏れたことを誰にも知られずに済みます。

この計画を成功させるには、次の問題を解決する必要があります。

• A 国が受け取る図には駅番号がなく、どの線路が本物か偽物かも示されていません。分かるのは印の付いた駅と、偽の線路をちょうど $K$ 本追加したことだけです。

• したがって送信側は、受信側が図だけから本物と偽物を区別できるよう、適切な位置に偽の線路を追加し、適切な駅に印を付ける必要があります。

• 受信側も送信側の変更方法を理解し、受け取った図から元の鉄道網の図を復元する必要があります。

このように、鉄道網の図を変更する関数と、その図から本物の鉄道網を復元する関数が必要です。A 国はこの仕事をあなたに任せたいと考えています。

実装の詳細

次の二つの関数を実装してください。

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• 整数引数 N は B 国の駅の数 $N$ です。駅は $1$ 以上 $N$ 以下の整数で表されます。

• 整数引数 K は追加する偽の線路の数 $K$ です。

• 引数 X は印を付ける駅の番号を記録します。関数終了時に、X は $1$ 以上 $N$ 以下の正の整数を保持していなければなりません。

• 引数の配列 E の要素数は $N-1$ で、B 国の鉄道網を表します。E の組 $(a,b)$ は駅 $a$ と $b$ が線路で直接つながっていることを表します。

• $K$ 個の組 $(a,b)$ を含む配列を返してください。各組は異なる駅 $a$ と $b$ を偽の線路で結ぶことを表します。駅 $a$ と $b$ が本物または偽物の線路で既につながっている場合、さらに偽の線路を追加することはできません。

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• 整数引数 N は B 国の駅の数 $N$ です。駅は $1$ 以上 $N$ 以下の整数で表されます。送信時に番号が消されたため、この関数の駅番号は実際の番号と異なる場合があります。つまり、encode_map で使った番号にある全単射を適用した番号です。

• 整数引数 K は追加された偽の線路の数 $K$ です。

• 整数引数 X は特別な印の付いた駅の番号です。

• 引数の配列 E の要素数は $N+K-1$ で、A 国に届いた図を表します。E の組 $(a,b)$ は駅 $a$ と $b$ が図で本物または偽物の線路によって直接つながることを表します。E の要素の順序には意味がありません。

• この関数は encode_map が作った図から元の図を復元します。B 国の鉄道網を表す $N-1$ 個の組 $(a,b)$ の配列を返してください。

提出するソースコードのどの部分でも入出力関数を呼び出してはいけません。

各テストケースには一つ以上の独立したシナリオが含まれます。$T$ 個のシナリオを含むテストケースでは、上記の関数を呼ぶプログラムが次のようにちょうど二回実行されます。

一回目の実行では：

• encode_map が $T$ 回呼ばれます。

• encode_map の結果が採点システムに保存されます。

• decode_map は呼ばれません。

二回目の実行では：

• decode_map が複数回呼ばれます。毎回、任意のシナリオが選ばれ、そのシナリオで encode_map が作った図が decode_map の入力になります。

• encode_map は呼ばれません。

この問題の実行時間とメモリ使用量は、二回の実行を合わせて計算されます。

制約

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

小課題

1.（$4$ 点）$N \le 4$。

2.（$13$ 点）$K=1$。

3.（$11$ 点）各駅につながる線路は高々二本です。

4.（$29$ 点）任意の駅から任意の別の駅へ、高々 $\lfloor N/2 \rfloor$ 本の線路を通って移動できます。

5.（$43$ 点）追加の制約はありません。

小課題

encode_map が正しい図を作り、decode_map が鉄道網を正確に復元した場合に限り、そのテストは正解です。特に、decode_map が返す配列に偽の線路が一本でも含まれると、そのテストの得点は $0$ です。encode_map と decode_map が返す配列の要素の順序は問いません。

各小課題の得点は、その小課題のすべてのテストの得点の最小値です。

入出力例

• $N=6$、$K=1$、線路 $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$ の場合を考えます。

採点プログラムは次の関数を呼びます。

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

左の図は B 国の鉄道網です。偽の線路 $(4,2)$ を追加し、駅 $1$ に印を付けると右の図になります。この場合、encode_map は [(4, 2)] を返し、X に $1$ を保存します。ほかの答えも存在し得ます。

次に、採点プログラムは次の関数を呼びます。最後の引数の配列の要素の順序は変わる場合があります。

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

入力の表す図を以下に示します。駅番号が encode_map のものと異なることに注意してください。

この関数は [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)] を返します。要素の順序は変わってもかまいません。

この例は小課題 $2$、$4$、$5$ の条件を満たします。

サンプル採点プログラム

サンプル採点プログラムは次の形式で入力を受け取ります。

• $1$ 行目：$T$

続いて、それぞれ一つのシナリオを表す $T$ 個のブロックがあります。各ブロックは次の形式です。

• $1$ 行目：$N\ K$

• $1+i$ 行目（$1 \le i \le N-1$）：$a_i\ b_i$

組 $a_i,b_i$ は、駅 $a_i$ と $b_i$ を結ぶ線路があることを表します。

サンプル採点プログラムは各シナリオについて次を出力します。

• $1$ 行目：encode_map が返した配列。

• $2$ 行目：decode_map が返した配列。

サンプル採点プログラムは実際の採点に使うものと異なる場合があります。