AT_bogosortcontest_div1_d Go Robots

$ N $ 頂点 $ 2(N-1) $ 辺の有向非巡回グラフが与えられます。 頂点 $ i \ (1 \leq i \leq N-1) $ からは辺 $ i \to L_i $ と $ i \to R_i $ が出ています。 グラフは自己ループを含みませんが、多重辺は存在する可能性があります。 また、頂点 $ i \ (1 \leq i \leq N-1) $ にはスイッチ $ S_i $ があり、はじめはすべて $ S_i = $ `L` です。 今から全部で $ K $ 体のロボットを順に頂点 $ 1 $ に放ちます。 ロボットが頂点 $ i \ (1 \leq i \leq N-1) $ に到達するとスイッチ $ S_i $ を反転させて、反転後のスイッチの方向の頂点に $ 1 $ 秒かけて進みます。 より厳密には、ロボットが時刻 $ t $ に頂点 $ i $ に到達したとき、以下のルールに従って $ S_i $ の更新と次の頂点への移動を行います。 - $ S_i = $ `L` のとき、 $ S_i = $ `R` に更新し、時刻 $ t+1 $ に頂点 $ R_i $ に到達する。 - $ S_i = $ `R` のとき、 $ S_i = $ `L` に更新し、時刻 $ t+1 $ に頂点 $ L_i $ に到達する。 時刻 $ 0 $ に $ 1 $ 体目のロボットを頂点 $ 1 $ に放ちます。 $ i \ (1 \leq i \leq K-1) $ 体目のロボットが頂点 $ N $ に到達した瞬間に $ i + 1 $ 体目のロボットを頂点 $ 1 $ に放ちます。 $ K $ 体目のロボットが頂点 $ N $ に到達した時刻を求めてください。 $ T $ 個のテストケースについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ L_{1} $ $ R_{1} $ $ L_{2} $ $ R_{2} $ $ \vdots $ $ L_{N-1} $ $ R_{N-1} $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて説明します。 はじめのスイッチ全体の状態は `LL` です。 時刻 $ 0 $ に $ 1 $ 体目のロボットが頂点 $ 1 $ に放たれ、スイッチ $ S_1 $ が更新されて全体の状態は `RL` になり、時刻 $ 1 $ にロボットは頂点 $ 3 $ に到達します。 次に時刻 $ 1 $ に $ 2 $ 体目のロボットが頂点 $ 1 $ に放たれ、スイッチ $ S_1 $ が更新されて全体の状態は `LL` になり、時刻 $ 2 $ にロボットは頂点 $ 2 $ に到達します。 その後、スイッチ $ S_{2} $ が更新されて全体の状態は `LR` になり、時刻 $ 3 $ にロボットが頂点 $ 3 $ に到達して終了します。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 2\times 10^5 $ - $ 1 \leq K \leq 10^{12} $ - $ i+1 \leq L_{i}, R_{i} \leq N \ (1 \leq i \leq N-1) $ - すべてのテストケースについての $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力される数値はすべて整数