IOI 国是一个由 $N$ 个城市组成的国家。这些城市编号为 $1, 2, \dots, N$。JOI 教授对 IOI 国道路网的建设过程产生了兴趣。
通过查阅 IOI 国的历史资料，JOI 教授了解到了以下情况：
- IOI 国的城市自建国以来至今保持不变。建国初期，城市之间没有任何道路。
- 在 IOI 国建国 $i$ 年后 ($1 \le i \le Q$)，制定了关于城市 $A_i$ 和城市 $B_i$ 之间交通状况的改善计划。
- 在制定的改善计划中，有些按计划执行了，而有些则被放弃，未予执行。
- 资料中明确记录了哪些改善计划被执行了。
- 所有被执行的改善计划均在 1 年内完成。
此外，从另一份文献中得知，关于城市 $A_i$ 和城市 $B_i$ 之间的交通状况改善计划内容如下：
- 如果在制定改善计划时，无法通过已建成的道路从城市 $A_i$ 到达城市 $B_i$，则在城市 $A_i$ 和城市 $B_i$ 之间新建一条双向道路。新建的道路是未铺装的。
- 如果在制定改善计划时，可以通过已建成的道路从城市 $A_i$ 到达城市 $B_i$，则在所有使用道路数量最少的路径中，将这些路径上包含的所有未铺装道路进行铺装。如果存在多条使用道路数量最少的路径，则对这些路径上的所有未铺装道路进行同样的铺装处理。已经铺装过的道路不会再次铺装。
为了进一步调查，JOI 教授决定针对每一个被放弃的改善计划，计算如果仅额外执行该项计划，在该计划中需要铺装多少条道路。
任务
给定 IOI 国的交通状况改善计划及其执行情况，请编写一个程序，针对每一个被放弃的改善计划，计算如果执行该计划，需要铺装多少条道路。
输入格式
从标准输入读取以下数据：
- 第 1 行包含两个整数 $N, Q$，以空格分隔。这表示 IOI 国有 $N$ 个城市，JOI 教授关注建国后 $Q$ 年间的交通状况改善计划。
- 接下来的 $Q$ 行中，第 $i$ 行 ($1 \le i \le Q$) 包含三个整数 $T_i, A_i, B_i$，以空格分隔。整数 $T_i$ 表示建国 $i$ 年后制定的改善计划的执行情况，$T_i = 1$ 表示该计划已执行，$T_i = 2$ 表示该计划未执行而被放弃。整数 $A_i, B_i$ 表示在建国 $i$ 年后制定了关于城市 $A_i$ 和城市 $B_i$ 之间交通状况的改善计划。
输出格式
输出到标准输出。对于每一个被放弃的改善计划，如果执行该计划，请在一行中输出需要铺装的道路数量。如果执行该计划会导致新建道路，则输出 -1。
数据范围
所有输入数据满足以下条件：
- $2 \le N \le 100\,000$
- $1 \le Q \le 300\,000$
- $1 \le T_i \le 2$ ($1 \le i \le Q$)
- $1 \le A_i \le N$ ($1 \le i \le Q$)
- $1 \le B_i \le N$ ($1 \le i \le Q$)
- $A_i \neq B_i$ ($1 \le i \le Q$)
子任务
子任务 1 [10 点]
满足以下条件： $N \le 1\,000$ $Q \le 3\,000$
子任务 2 [25 点]
- 存在整数 $P$ ($1 \le P \le Q - 1$)，满足 $T_i = 1$ ($1 \le i \le P$) 且 $T_i = 2$ ($P + 1 \le i \le Q$)。
子任务 3 [25 点]
- 对于所有满足 $T_i = 1$ 的 $i$ ($1 \le i \le Q$)，以下任一条件成立：
- 在执行建国 $i$ 年后的改善计划之前，无法通过已建成的道路从城市 $A_i$ 到达城市 $B_i$。
- 在执行建国 $i$ 年后的改善计划之前，可以通过已建成的道路中不超过 200 条道路从城市 $A_i$ 到达城市 $B_i$。
子任务 4 [25 点]
- 满足 $T_i = 2$ 的 $i$ ($1 \le i \le Q$) 不超过 200 个。
子任务 5 [15 点]
- 无附加限制。
样例
样例输入 1
3 7 1 1 2 2 2 1 2 2 3 1 2 1 2 1 2 1 2 3 2 1 3
样例输出 1
1 -1 0 1
样例输入 2
6 8 1 1 3 1 6 1 1 2 5 2 3 6 1 3 6 1 4 1 2 4 3 2 2 5
样例输出 2
2 1 1
样例输入 3
7 11 1 5 1 1 6 2 1 1 3 1 3 5 1 5 7 1 4 5 1 4 1 2 1 3 2 3 7 2 4 3 2 5 6
样例输出 3
0 1 0 -1