图+bfs

每个车站作为一个节点，记录编号，以及与之直接相连的两个站点。

结果是几个独立的环。

将每个环染色，以便判断是否可达（属于不同环的站点必然不可达），同时记录每个环的长度。

若两站点可达，任选一个方向记录两点距离，与走另一方向距离比较（环长-已记录的距离），选小的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int color[maxn];
int len_color[maxn/2];
int num_color=0;
int N, q;
struct Node {
	int index;
	vector<Node*>neighbour;
}node[maxn];
typedef pair<Node*, int> pni;
int len_now = 0;
void paint_1(Node* a) {
	if (color[a->index] != -1)
		return;
	len_now++;
	color[a->index] = num_color;
	for (auto c : a->neighbour) {
		if (color[c->index] == -1) {
			paint_1(c);
		}
	}
}
void paint(Node* a) {
	len_now = 0;
	paint_1(a);
	len_color[num_color] = len_now;
	num_color++;
}
bool operator<(pni a, pni b) {
	return a.second < b.second;
}
bool visited[maxn];
int find(Node* a,Node* b) {
	memset(visited, 0, N+2);
	priority_queue<pni>pr;
	pr.push(pni(a, 0));
	Node* tmp = a;
	while (!pr.empty()) {
		pni tp = pr.top();
		Node* front = tp.first;
		pr.pop();
		for (auto c : front->neighbour) {
			if (!visited[c->index]) {
				visited[c->index] = true;
				if (c == b)
					return tp.second + 1;
				pr.push(pni(c, tp.second + 1));
			}
		}
	}


}
int main() {
	cin >> N >> q;
	for (int i = 0; i <= N; i++) {
		node[i].index = i;
	}
	fill(color, color + N+2, -1);
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		node[a].neighbour.push_back(node+b);
		node[b].neighbour.push_back(node+a);
	}
	for (int i = 0; i < q; i++) {
		int u, v;
		cin >> u >> v;
		if (color[u] == -1) {
			paint(node + u);
		}
		if (color[v] == -1) {
			paint(node + v);
		}
		if (color[u] != color[v]) {
			cout << -1 << endl;
			continue;
		}
		int dis = find(node + u, node + v);
		int ans = min(dis, len_color[color[u]] - dis);
		cout << ans << endl;
	}
	return 0;
}