다리

상트페테르부르크 시의 수로 길이의 총합은 약 282 km이고, 도시 면적 중 물이 차지하는 비중은 약 7%이다.

---

Wikipedia

상트페테르부르크는 섬 $n$개를 다리 $m$개로 이어 만든 도시이다. 섬은 1부터 $n$까지의 정수로, 다리는 1부터 $m$까지의 정수로 나타낸다. 각 다리는 서로 다른 두 섬을 잇는다. 어떤 다리는 표트르 대제 시절에 지었고, 어떤 다리는 지은 지 얼마 되지 않았다. 그래서 다리마다 무게 제한이 다르다. 즉, 자동차가 다리 $i$를 지나려면 무게가 $d_i$ 이하여야 한다. 다리는 때때로 보수한다. 다만 보수한다고 해서 다리가 반드시 튼튼해지는 것은 아니어서, $d_i$ 값은 늘 수도 있고 줄어들 수도 있다. 시민과 관광객을 위해 다음 두 가지 질의를 처리할 수 있는 프로그램이 있다면 좋을 것이다.

1. 다리 $b_j$의 무게 제한이 $r_j$로 바뀌었다.
2. 무게가 $w_j$인 자동차가 섬 $s_j$에서 출발해 도착할 수 있는 섬의 수를 구하시오.

두 번째 형태의 질의에 모두 답하시오.

첫 번째 줄에는 두 정수 $n$, $m$이 주어진다. 각각 상트페테르부르크의 섬 수와 다리 수이다. ($1 \le n \le 50000$, $0 \le m \le 100000$)

다음 $m$개 줄 중 $i$번째 줄에는 세 정수 $u_i$, $v_i$, $d_i$가 주어진다. 섬 $u_i$와 섬 $v_i$를 잇는 다리의 처음 무게 제한은 $d_i$이다. ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le d_i \le 10^9$)

그다음 줄에는 질의의 수 $q$가 주어진다. ($1 \le q \le 100000$) 이어서 $q$개 줄에 질의가 주어진다. 각 질의는 정수 $t_j$로 시작한다. ($t_j \in \{1, 2\}$)

$t_j = 1$이면 첫 번째 형태의 질의이다. 정수 $b_j$, $r_j$가 뒤따르며, 다리 $b_j$의 무게 제한이 $r_j$로 바뀐다는 뜻이다. ($1 \le b_j \le m$, $1 \le r_j \le 10^9$)

$t_j = 2$이면 두 번째 형태의 질의이다. 정수 $s_j$, $w_j$가 뒤따르며, 무게가 $w_j$인 자동차가 섬 $s_j$에서 출발해 도착할 수 있는 섬의 수를 구하라는 뜻이다. ($1 \le s_j \le n$, $1 \le w_j \le 10^9$)

두 번째 형태의 질의마다 한 줄에 답을 하나씩 출력한다.

녹색 에지는 질의에서 물어보는 자동차가 건널 수 있는 다리를 나타낸다. 녹색 노드는 이 자동차가 도착할 수 있는 섬을 나타낸다. 화살표가 가리키는 섬은 이 자동차가 처음에 있던 곳이다.

첫 번째 테스트 데이터

두 번째 테스트 데이터