AT_tupc2024_b Matching Query

$ 0 $ 以上 $ M $ 未満の整数からなる長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ Q $ 個のクエリが与えられるので順に処理してください。 $ i $ 番目のクエリは以下で説明されます。 - 整数 $ x_i,y_i $ が与えられる。 $ A $ の $ x_i $ 番目の要素を $ y_i $ で更新する。その後、以下の問題を解け。 - 整数列 $ A $ をもとにして頂点数 $ N $ の無向グラフ $ G $ を作る。頂点には $ 1,2,\ldots,N $ までの番号がつけられており、頂点 $ u,v\ (1\leq u\lt v\leq N) $ の間には $ A_u+1\equiv A_v\ (\mathrm{mod}\ M) $ が成り立つとき辺が張られる。 $ G $ の最大マッチングの大きさを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_Q $ $ y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 個目のクエリの答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - 追加の制約 $ Q=1 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - 追加の制約 $ M\leq 100 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ つ目のクエリについて、 $ A_6 $ が $ 0 $ に更新され $ A=(1,1,0,2,0,0) $ になります。 $ G $ には頂点 $ 1,4 $ の間と頂点 $ 2,4 $ の間と頂点 $ 4,5 $ の間と頂点 $ 4,6 $ の間に辺が張られるため、 $ G $ の最大マッチングの大きさは $ 1 $ です。 $ 2 $ つ目のクエリについて、 $ A_4 $ が $ 1 $ に更新され $ A=(1,1,0,1,0,0) $ になります。 $ G $ には頂点 $ 3,4 $ の間に辺が張られるため、 $ G $ の最大マッチングの大きさは $ 1 $ です。 ### Constraints - $ 2\leq N\leq 3\times 10^5 $ - $ 1\leq Q\leq 3\times 10^5 $ - $ 2\leq M\leq 3\times 10^5 $ - $ 0\leq A_i\lt M $ - $ 1\leq x_i\leq N $ - $ 0\leq y_i\lt M $ - 入力は全て整数