P15665 [ICPC 2025 Jakarta R] Travelling Taro Trains

Taro is travelling within a country, which consists of $N$ cities numbered from $1$ to $N$. There are also $K$ train companies, numbered from $1$ to $K$, that operate the trains within the nation. Initially, there are $M$ one-way train services, each of which can be described as a triple $(u, v, k)$, meaning that there are trains operated by company $k$ that goes from city $u$ to city $v$. Taro is currently in city $1$. In the next $Q$ months, one of the following three events may happen. - $\texttt{1 u v k}$: company $k$ $\textbf{starts}$ a new train service that goes from city $u$ to city $v$. In other words, add $(u, v, k)$ to the train network. - $\texttt{2 u v k}$: company $k$ $\textbf{ends}$ its train service that goes from city $u$ to city $v$. In other words, remove $(u, v, k)$ from the train network. - $\texttt{3 k}$: Taro either $\textbf{stays}$ in the city he is currently in, or $\textbf{takes}$ one of the trains operated by company $k$ from the city he is currently in to another city. It is guaranteed to you that the existing services $(u, v, k)$ are always distinct throughout the course of events, and event $2$ always removes a currently existing service. Every time an event $3$ happens, find the number of different cities Taro can possibly be in, given the course of events so far.

The first line contains three integers $N$, $M$, $K$, and $Q$ ($2 \le N \le 300\;000$; $1 \le M, K, Q \le 300\;000$). Each of the next $M$ lines contains three integers $u$, $v$, $k$ ($1 \leq u, v \leq N$; $1 \leq k \leq K$; $u \neq v$) describing the initial train services. Each of the next $Q$ lines contains an event as described above. The input guarantees that the existing services $(u, v, k)$ are always distinct throughout the event.

For each event $3$, output, in a single line, the number of different cities Taro can possibly be in.

$\textit{Explanation of Sample 1:}$ Initially, Taro is in city $1$. - In the first event $3$, there are no train services operated by company $2$ that departs from city $1$, so Taro has to stay in city $1$. - In the second event $3$, Taro can either stay in city $1$, or take the service $(1, 3, 1)$ and end in city $3$. Because Taro can be in either city $1$ or $3$, you have to output $2$. - In the third event $3$, the existing train services are $(1, 3, 1)$, $(1, 4, 2)$, $(3, 2, 2)$, $(3, 5, 2)$. If Taro is currently in city $1$, he can take service $(1, 4, 2)$ and end in city $4$. If Taro is currently in city $3$, he can take services $(3, 2, 2)$ or $(3, 5, 2)$ and end in city $2$ or $5$ respectively. Since he can possibly in city $1$, $2$, $3$, $4$, and $5$, you have to output $5$.