题目描述

小明是蓝桥部队的长官，他的班上有 N 名军人和 1 名军师。

这天，N 名军人在操场上站成一排，起初编号为 i 的军人站在第 i 列。

作为长官，小明可以对军人和军师下达 M 条命令，命令有两种类型，格式如下：

• 1 x y，让军人 x 所在列的所有人作为一个整体移动到和军人 y 所在列的后面，使两列合并为一列。

• 2 x y，询问军师军人 x 和军人 y 是否站在同一列。若是，则军师要回应小明 x,y 之间有多少人，否则军师要回应 −1。

你就是小明的军师，请你回答小明的每个询问。

输入描述

输入第 11 行包含两个正整数 N,M，分别表示军人的数量和小明的命令条数。

第2∼M+1 行每行表示一条命令。

2≤N≤105，1≤M≤3×105，1≤x,y≤N。

输出描述

对于每个询问，输出一行表示答案。

输入输出样例

示例 1

输入

3 5
2 1 2
1 2 1 
2 1 2
1 1 3
2 2 3 

输出

-1
0
1

运行限制

• 最大运行时间：3s

• 最大运行内存: 256M

源码：

import java.util.Scanner;public class 蓝桥部队 {static int[] parent;static int[] rank;static int[] d;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();//初始化size，d，p数组rank = new int[n+1];parent = new int[n+1];d = new int[n+1];for (int i = 1; i <= n; i++) {rank[i] = 1;parent[i] = i;d[i] = 0;}//读取操作for (int i = 0; i < m; i++) {int op = scanner.nextInt();int x = scanner.nextInt();int y = scanner.nextInt();if(op == 1) {//join函数int px = find(x);int py = find(y);if(px != py) {parent[px] = py;d[px] = rank[py];rank[py] += rank[px];}}else {int px = find(x);int py = find(y);if(px != py) {System.out.println("-1");}else {                System.out.println(Math.max(0, Math.abs(d[x]-d[y])-1));}}}}private static int find(int x) {if (parent[x]!=x) {int root=find(parent[x]);d[x]+=d[parent[x]];parent[x]=root;}return parent[x];}}