Description：

给一个多边形的三角剖分，多次询问两点间最短路。

$1\leqslant n\leqslant 50000$

Solution：

先找出所有的三角形，具体来说是类似拓扑排序每次找到一个度数为 $2$ 的点然后丢进队列里，然后减掉它的出边的度数，然后我们就可以给每个三角形编号，建出来对偶图会发现我们得到了一棵树，然后对这棵树边分治，然后再用类似ZJOI2016的方法计算就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 50010

struct edge

{

	int to,nxt;

}e[MAXN * 4];

int edgenum = 0;

int lin[MAXN] = {0};

int deg[MAXN];

void add(int a,int b)

{

	++deg[a];++deg[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct edges

{

	int u,v;

}es[MAXN];

int t[MAXN][4];

int tot = 0;

bool tag[MAXN];

struct edgev

{

	int to,nxt,a,b;

}ev[MAXN << 1];

int edgenumv = 1;

int linv[MAXN] = {0};

void addv(int a,int b,int l,int r)

{

	ev[++edgenumv] = (edgev){b,linv[a],l,r};linv[a] = edgenumv;

	ev[++edgenumv] = (edgev){a,linv[b],l,r};linv[b] = edgenumv;

	return;

}

map<pair<int,int>,int> f;

#define MAXQ (MAXN << 1)

struct query

{

	int u,v,id;

}q[MAXQ],q_[MAXQ];

int ans[MAXQ];

int s,mx,edg;

#define INF 0x3f3f3f3f

bool ban[MAXN << 1];

int siz[MAXN];

void getedg(int k,int fa)

{

	siz[k] = 1;

	for(int i = linv[k];i != 0;i = ev[i].nxt)

	{

		if(ban[i] || ev[i].to == fa)continue;

		getedg(ev[i].to,k);

		siz[k] += siz[ev[i].to];

		int d = max(siz[ev[i].to],s - siz[ev[i].to]);

		if(d < mx)edg = i,mx = d;

	}

	return;

}

void calcsiz(int k,int fa)

{

	siz[k] = 1;

	for(int i = linv[k];i != 0;i = ev[i].nxt)

	{

		if(ban[i] || ev[i].to == fa)continue;

		calcsiz(ev[i].to,k);

		siz[k] += siz[ev[i].to];

	}

	return;

}

int gete(int k,int s_)

{

	s = s_;edg = -1;mx = INF;

	getedg(k,0);

	return edg;

}

namespace SP

{

	bool vis[MAXN];

	int d[MAXN];

	void dijkstra(int k)

	{

		priority_queue< pair<int,int> > q;

		q.push(make_pair(0,k));d[k] = 0;

		while(!q.empty())

		{

			int k = q.top().second;q.pop();//cout << k << " " << d[k] << endl;

			if(vis[k])continue;vis[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(!vis[e[i].to] && d[e[i].to] > d[k] + 1)

				{

					d[e[i].to] = d[k] + 1;

					q.push(make_pair(-d[e[i].to],e[i].to));

				}

			}

		}

		return;

	}

}

int col[MAXN];

void mark(int k,int fa,int v)

{

	SP::vis[t[k][1]] = SP::vis[t[k][2]] = SP::vis[t[k][3]] = false;

	SP::d[t[k][1]] = SP::d[t[k][2]] = SP::d[t[k][3]] = INF;

	col[t[k][1]] = col[t[k][2]] = col[t[k][3]] = v;

	for(int i = linv[k];i != 0;i = ev[i].nxt)

	{

		if(ban[i] || ev[i].to == fa)continue;

		mark(ev[i].to,k,v);

	}

	return;

}

void divide(int k,int l,int r)

{

	calcsiz(k,0);

	if(siz[k] == 1){for(int i = l;i <= r;++i)ans[q[i].id] = (q[i].u != q[i].v);return;}

	int ed = gete(k,siz[k]);

	ban[ed] = ban[ed ^ 1] = true;

	int u = ev[ed].to,v = ev[ed ^ 1].to;

	int a = ev[ed].a,b = ev[ed].b;//cout << u << " " << v << " " << a << " " << b << " : " << endl;

	mark(u,0,0);mark(v,0,1);

	col[a] = col[b] = -1;

	SP::dijkstra(a);

	for(int k = l;k <= r;++k)ans[q[k].id] = min(ans[q[k].id],SP::d[q[k].u] + SP::d[q[k].v]);

	//for(int k = l;k <= r;++k)cout << q[k].u << " " << q[k].v << " " << SP::d[q[k].u] << " " << SP::d[q[k].v] << endl;

	mark(u,0,0);mark(v,0,1);

	col[a] = col[b] = -1;

	SP::dijkstra(b);

	for(int k = l;k <= r;++k)ans[q[k].id] = min(ans[q[k].id],SP::d[q[k].u] + SP::d[q[k].v]);

	int curl = l,curr = r;

	for(int k = l;k <= r;++k)

	{

		if(col[q[k].u] == 0 && col[q[k].v] == 0)q_[curl++] = q[k];

		if(col[q[k].u] == 1 && col[q[k].v] == 1)q_[curr--] = q[k];

	}

	for(int k = l;k <= r;++k)q[k] = q_[k];

	divide(u,l,curl - 1);divide(v,curr + 1,r);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)add(i,i % n + 1);

	for(int i = 1;i <= n - 3;++i)add(es[i].u = rd(),es[i].v = rd());

	queue<int> qu;

	for(int i = 1;i <= n;++i)if(deg[i] == 2)qu.push(i);

	while(!qu.empty())

	{

		int k = qu.front();qu.pop();

		tag[k] = true;

		t[++tot][1] = k;t[tot][0] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(tag[e[i].to])continue;

			t[tot][++t[tot][0]] = e[i].to;

			if((--deg[e[i].to]) == 2)qu.push(e[i].to);

		}

		sort(t[tot] + 1,t[tot] + 1 + 3);

	}

	for(int i = 1;i <= n - 2;++i)

	{

		pair<int,int> k;

		k = make_pair(t[i][1],t[i][2]);

		if(f.find(k) == f.end())f[k] = i;

		else addv(f[k],i,t[i][1],t[i][2]);

		k = make_pair(t[i][1],t[i][3]);

		if(f.find(k) == f.end())f[k] = i;

		else addv(f[k],i,t[i][1],t[i][3]);

		k = make_pair(t[i][2],t[i][3]);

		if(f.find(k) == f.end())f[k] = i;

		else addv(f[k],i,t[i][2],t[i][3]);

	}

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)q[i].u = rd(),q[i].v = rd(),q[i].id = i;

	memset(ans,0x3f,sizeof(ans));

	for(int i = 1;i <= n;++i)SP::vis[i] = true;

	divide(1,1,m);

	for(int i = 1;i <= m;++i)printf("%d\n",ans[i]); 

	return 0;

}