题目描述

太郎正在一个国家旅行，该国家由编号为 $1$ 到 $N$ 的 $N$ 个城市组成。国内还有 $K$ 家铁路公司，编号为 $1$ 到 $K$，负责运营火车。初始时，有 $M$ 条单向火车线路，每条线路可以用一个三元组 $(u, v, k)$ 描述，表示存在由公司 $k$ 运营的从城市 $u$ 开往城市 $v$ 的火车。

太郎当前位于城市 $1$。在接下来的 $Q$ 个月中，可能会发生以下三种事件之一。

• $\texttt{1 u v k}$：公司 $k$ 开通一条从城市 $u$ 到城市 $v$ 的新火车线路。换句话说，将 $(u, v, k)$ 加入铁路网络。
• $\texttt{2 u v k}$：公司 $k$ 停运其从城市 $u$ 到城市 $v$ 的火车线路。换句话说，从铁路网络中移除 $(u, v, k)$。
• $\texttt{3 k}$：太郎可以选择停留在他当前所在的城市，或者乘坐一趟由公司 $k$ 运营的、从他当前所在城市开往另一个城市的火车。

题目保证在整个事件过程中，现有的线路 $(u, v, k)$ 始终互不相同，且事件 $2$ 总是移除一条当前存在的线路。

每当事件 $3$ 发生时，根据到目前为止的事件过程，求太郎可能位于的不同城市的数量。

输入格式

第一行包含四个整数 $N$、$M$、$K$ 和 $Q$（$2 \le N \le 300\;000$；$1 \le M, K, Q \le 300\;000$）。

接下来的 $M$ 行，每行包含三个整数 $u$、$v$、$k$（$1 \leq u, v \leq N$；$1 \leq k \leq K$；$u \neq v$），描述初始的火车线路。

接下来的 $Q$ 行，每行描述一个如上所述的事件。

输入保证在整个事件过程中，现有的线路 $(u, v, k)$ 始终互不相同。

输出格式

对于每个事件 $3$，输出一行，表示太郎可能位于的不同城市的数量。

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
2
5

提示

样例 1 解释： 初始时，太郎位于城市 $1$。

• 在第一个事件 $3$ 中，没有从城市 $1$ 出发、由公司 $2$ 运营的火车线路，因此太郎必须停留在城市 $1$。
• 在第二个事件 $3$ 中，太郎可以选择停留在城市 $1$，或者乘坐线路 $(1, 3, 1)$ 到达城市 $3$。因为太郎可能位于城市 $1$ 或 $3$，所以输出 $2$。
• 在第三个事件 $3$ 中，现有的火车线路为 $(1, 3, 1)$、$(1, 4, 2)$、$(3, 2, 2)$、$(3, 5, 2)$。如果太郎当前在城市 $1$，他可以乘坐线路 $(1, 4, 2)$ 到达城市 $4$。如果太郎当前在城市 $3$，他可以乘坐线路 $(3, 2, 2)$ 或 $(3, 5, 2)$ 分别到达城市 $2$ 或 $5$。由于他可能位于城市 $1$、$2$、$3$、$4$ 和 $5$，因此输出 $5$。

翻译由 DeepSeek V3.2 完成