問題文

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 個のテストケースについて答えてください。

制約

• 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 以下
• 入力される数値はすべて整数

入力例 1

4
3 2
2 3
3 3
2 10
2 2
4 5
2 3
3 4
4 4
10 1000000000000
2 4
3 4
5 6
6 5
8 7
7 8
10 9
9 10
10 10

出力例 1

3
10
11
5000000000000

1 つ目のテストケースについて説明します。

はじめのスイッチ全体の状態は LL です。

時刻 0 に 1 体目のロボットが頂点 1 に放たれ、スイッチ S_1 が更新されて全体の状態は RL になり、時刻 1 にロボットは頂点 3 に到達します。

次に時刻 1 に 2 体目のロボットが頂点 1 に放たれ、スイッチ S_1 が更新されて全体の状態は LL になり、時刻 2 にロボットは頂点 2 に到達します。

その後、スイッチ S_{2} が更新されて全体の状態は LR になり、時刻 3 にロボットが頂点 3 に到達して終了します。