P9638 "yyOI R1" youyou's Military Training

In youyou's class, height may be a sensitive topic.

There are $n$ students in youyou's class and $m$ pairs of friends. For the $i$-th friend relationship, there is a sensitivity value $k_i$ related to height, and the sensitivity value may change. We define that if two students are **friends**, then there must exist some relationship that **directly** connects these two students. We define that if two students are **close friends**, then there must exist a direct or indirect relationship that connects these two students. For example, if there are relationships $(1,2)$ and $(2,3)$, then $1$ and $2$ are friends, but $1$ and $3$ are close friends. Now, military training is about to begin. Students need to collect their training uniforms. If a student receives a uniform of size $p$, then all students will break friendships with those friends whose relationship sensitivity value is less than $p$. That is, for every friend relationship, if its sensitivity value is less than $p$, then this friend relationship will be disconnected. However, when the next student receives a uniform, all friendships that were disconnected **previously** will be restored. Since collecting uniforms is a complicated process and youyou is very interested in it, there are $q$ operations in total, and there are three types of operations: - Operation $1$, in the form `1 x`, means a student receives a uniform of size $x$. - Operation $2$, in the form `2 x`, asks how many close friends student $x$ still has (including themself). - Operation $3$, in the form `3 x y`, means the sensitivity value of the $x$-th friend relationship becomes $y$. In particular, **the relative order of sensitivity values will not change$^*$** (see details below), and any relationships that have already been disconnected will not be restored. **Note: "close friends" and "friends" are two different concepts. Friends are always close friends, but close friends are not necessarily friends.** $^*$: "The relative order does not change" means that among all current sensitivity values, the modified sensitivity value has the **same rank** as the original one. For example, if the original sensitivity values among all friend pairs are $\{1,2,3,5,6\}$, the rank of $3$ is $3$, so $3$ can only be changed to one of $3,4$ in order to keep the rank unchanged, i.e. its position in the relative order does not change.

The first line contains three positive integers $n,m,q$. In the next $m$ lines, $m$ friend relationships are given. For the $i$-th line, three positive integers $x_i,y_i,k_i$ are given. In the last $q$ lines, $q$ operations are given. For each operation, a positive integer $op$ is given, indicating the operation type. When $op=1$, one more positive integer $x$ is given, meaning a student receives a uniform of size $x$. When $op=2$, one more positive integer $x$ is given, meaning a query. When $op=3$, two more positive integers $x,y$ are given, meaning an update.

For each query operation, output an integer $x$, meaning how many **close friends** the queried student has (**including themself**). It is guaranteed that for every test point, there is at least one query operation.

# Sample Explanation #1 As shown in the figure, this is the initial relationship graph.  The first operation is: a student receives a uniform of size $26963$, so all edges in the graph will be disconnected. The next operation: the weight of the third friend pair, i.e. edge $(2,3)$, becomes $40$. The next operation: query the number of close friends of student $4$. Since there are no existing edges, the answer is $1$. # Constraints | Test Point ID | $n$ | $q$ | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1,2$ | $\le 10$ | $\le 4 \times 10^5$ | None | | $3$ | $\le 10^3$ | $\le 10^3$ | None | | $4$ | $\le 10^5$ | $\le 4 \times 10^5$ | No operation $3$ | | $5,6$ | $\le 10^5$ | $\le 10^3$ | None | | $7$ | $\le 10^5$ | $\le 4 \times 10^5$ | No operation $1$ | | $8,9,10$ | $\le 4 \times 10^5$ | $\le 4 \times 10^5$ | None | Let $c_i$ denote the uniform size received in operation type $1$ in a query context, and let $e_i$ denote the sensitivity value after a modification. For $100\%$ of the data, $1 \le n,m,q,x_i,y_i \le 4 \times 10^5$, $1 \le k_i,c_i,e_i \le 1 \times 10^9$, and $m \le \min\{\frac{n(n-1)}{2},4 \times 10^5\}$. Also, the data guarantees that at any moment, all sensitivity values among all friend relationships are **pairwise distinct**. **Please pay attention to the impact of constant factors on time and memory usage.** Translated by ChatGPT 5