该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

历史线路查询

题目描述

某地区有 $N$ 个站点，编号为 $1$ 到 $N$。站点之间通过若干条通信线路连接。由于线路老化会影响通信质量，系统在某些查询中只允许使用较新的线路。

第 $i$ 条线路连接站点 $a_i$ 和站点 $b_i$，建成时间为 $y_i$ 年。线路是双向的。

现在有 $Q$ 次查询。每次查询给出一个起始站点 $v_j$ 和一个年份限制 $w_j$。在本次查询中，只能使用建成时间严格晚于 $w_j$ 年的线路，也就是说，建成时间为 $w_j$ 年或更早的线路都不能使用。

请你对每次查询，求出从站点 $v_j$ 出发，能够到达多少个站点。起始站点本身也计入答案。

输入格式

第一行包含两个整数 $N, M$，分别表示站点数量和线路数量。

接下来 $M$ 行，每行包含三个整数 $a_i, b_i, y_i$，表示一条连接 $a_i$ 和 $b_i$ 的双向线路，建成时间为 $y_i$ 年。

接下来一行包含一个整数 $Q$，表示查询次数。

接下来 $Q$ 行，每行包含两个整数 $v_j, w_j$，表示一次查询：从站点 $v_j$ 出发，只能使用建成时间严格晚于 $w_j$ 年的线路。

数据范围

• $1 \leq N \leq 100000$
• $0 \leq M \leq 200000$
• $1 \leq a_i,b_i \leq N$
• $a_i \neq b_i$
• $1 \leq y_i \leq 200000$
• $1 \leq Q \leq 100000$
• $1 \leq v_j \leq N$
• $0 \leq w_j \leq 200000$

图中可能存在重边，也可能存在即使使用所有线路也无法互相到达的站点。

输出格式

输出 $Q$ 行。

第 $j$ 行输出第 $j$ 次查询的答案，即从站点 $v_j$ 出发能够到达的站点数量。

输入输出样例 #1

输入 #1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

输出 #1

1
3
5

说明/提示

对于第 $1$ 次查询，只能使用建成时间晚于 $2000$ 年的线路。站点 $1$ 连接到站点 $2$ 的线路建成于 $2000$ 年，不能使用，因此只能到达站点 $1$ 本身。

对于第 $2$ 次查询，只能使用建成时间晚于 $1999$ 年的线路。从站点 $1$ 可以到达站点 $2$ 和站点 $3$，因此答案为 $3$。

对于第 $3$ 次查询，只能使用建成时间晚于 $1995$ 年的线路。所有线路都满足条件，因此可以到达全部 $5$ 个站点。