問題文

N 頂点 M 辺の連結な単純無向グラフが与えられます。グラフの頂点には、 それぞれ 1 から N までの番号が振られています。 i 番目の辺は、頂点 a_i と b_i を双方向に結んでいます。

10^9 種類の色があり、各色には 1 から 10^9 までの番号が振られています。 最初、すべての頂点は色 1 で塗られています。

以下の形式のクエリが Q 個与えられるので、順に処理してください。

• 整数 x, y が与えられる。現在の頂点 x の色の番号を出力し、頂点 x とそれに隣接するすべての頂点を色 y で塗り替える。

制約

• 1 \leq N \leq 200000
• N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 200000)
• 1 \leq a_i, b_i \leq N
• 1 \leq Q \leq 200000
• 1 \leq x_i \leq N
• 1 \leq y_i \leq 10^9
• 与えられるグラフは単純グラフである
• 与えられるグラフは連結である
• 入力はすべて整数で与えられる

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. (2 点)： N, Q \leq 2000
2. (4 点)： 追加の制約はない。

入力例 1

4 4
1 2
1 3
1 4
2 3
5
4 2
3 3
2 4
4 5
1 6

出力例 1

1
1
3
2
5

各クエリでは以下の処理が行われます。

• 1 番目のクエリでは、頂点 4 の色の番号 1 を出力した後、頂点 1, 4 を色 2 に変更する
• 2 番目のクエリでは、頂点 3 の色の番号 1 を出力した後、頂点 1, 2, 3 を色 3 に変更する
• 3 番目のクエリでは、頂点 2 の色の番号 3 を出力した後、頂点 1, 2, 3 を色 4 に変更する
• 4 番目のクエリでは、頂点 4 の色の番号 2 を出力した後、頂点 1, 4 を色 5 に変更する
• 5 番目のクエリでは、頂点 1 の色の番号 5 を出力した後、頂点 1, 2, 3, 4 を色 6 に変更する

入力例 2

10 20
1 3
7 8
5 8
2 3
7 10
6 7
4 7
9 5
6 5
2 9
4 2
5 7
3 10
4 8
1 8
10 8
5 3
9 1
7 3
2 1
10
3 5
2 2
8 9
5 3
8 2
3 9
7 1
7 1
8 4
6 8

出力例 2

1
5
1
9
3
3
9
1
1
1