35176번 - Travelling Taro Trains 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 6 | 6 | 6 | 100.000% |
문제
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.
1 u v k: company $k$ starts a new train service that goes from city $u$ to city $v$. In other words, add $(u, v, k)$ to the train network.2 u v k: company $k$ ends its train service that goes from city $u$ to city $v$. In other words, remove $(u, v, k)$ from the train network.3 k: Taro either stays in the city he is currently in, or 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 300000$; $1 \le M, K, Q \le 300000$). 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.
예제 입력 1
6 4 2 5 1 3 1 3 6 2 3 2 2 3 5 2 3 2 3 1 1 1 4 2 2 3 6 2 3 2
예제 출력 1
1 2 5
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$.