Description：

一个无向连通图， $n $ 个点， $m $ 条边，每条边有一个颜色。 保证无自环，没有长度超过 $ 2 $ 的简单环。现有 $ q $ 个询问：给出两个点 $ x,y$ ，选择一条 $ x $ 到 $ y $ 简单路径，价值为相同颜色的极大连续段个数，求出最大的价值。

$1\leqslant n\leqslant $

Solution：

首先发现图是一棵有重边的树，那就可以用树上的算法来做，然后又发现一条边只要有三种颜色，就可以随意切换，于是实际上只要每条边存三个不同颜色即可，我用的 $vector+unique$ 实现，最后树上倍增就行了，合并的复杂度是 $O(81)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	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,q;

#define MAXN 100010

#define MAXM 300010

map<pair<int,int>,vector<int> > es;

struct edge

{

	int to,nxt;

	vector<int> v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,vector<int> v)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = v;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = v;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool v[MAXN];

int fa[MAXN],fae[MAXN];

int dep[MAXN];

void dfs(int k)

{

	v[k] = true;

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

	{

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

		fa[e[i].to] = k;

		fae[e[i].to] = i;

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

		dfs(e[i].to);

	}

	v[k] = false;

	return;

}

struct skip

{

	int v[3][3];

	int a[3],b[3];

	int id;

	skip()

	{

		memset(a,0,sizeof(a));

		memset(b,0,sizeof(b));

	}

}f[MAXN][17];

inline skip merge(skip a,skip b)

{

	if(b.a[0] == 0)return a;

	register skip res;memset(res.v,0,sizeof(res.v));

	for(register int i = 0;i < 3;++i)if(a.a[i] != 0)

		for(register int j = 0;j < 3;++j)if(a.b[j] != 0)

			for(register int k = 0;k < 3;++k)if(b.a[k] != 0)

				for(register int l = 0;l < 3;++l)if(b.b[l] != 0)

					res.v[i][l] = max(res.v[i][l],a.v[i][j] + b.v[k][l] - (a.b[j] == b.a[k]));

	res.id = a.id;

	for(register int i = 0;i < 3;++i)

		if(a.a[i] != 0)res.a[i] = a.a[i];

	for(register int i = 0;i < 3;++i)

		if(b.b[i] != 0)res.b[i] = b.b[i];

	return res;

}

#define fi first

#define se second

#define INF 0x3f3f3f3f

inline int query(int a,int b)

{

	if(a == b)return 0;

	if(dep[a] < dep[b])swap(a,b);

	register skip ra,rb;

	for(register int i = 16;i >= 0;--i)

	{

		if(dep[f[a][i].id] >= dep[b])

		{

			ra = merge(f[a][i],ra);

			a = f[a][i].id;

		}

	}

	if(a == b)

	{

		register int ans = 0;

		for(register int i = 0;i < 3;++i)for(int j = 0;j < 3;++j)

			if(ra.a[i] != 0 && ra.b[j] != 0)

				ans = max(ans,ra.v[i][j]);

		return ans;

	}

	for(register int i = 16;i >= 0;--i)

	{

		if(f[a][i].id != f[b][i].id)

		{

			ra = merge(f[a][i],ra);a = f[a][i].id;

			rb = merge(f[b][i],rb);b = f[b][i].id;

		}

	}

	ra = merge(f[a][0],ra);

	rb = merge(f[b][0],rb);

	register int ans = 0;

	register int lef[3] = {0},lc[3],rig[3] = {0},rc[3];

	for(register int i = 0;i < 3;++i)if(ra.a[i] != 0)

		for(register int j = 0;j < 3;++j)if(ra.b[j] != 0)

			if(ra.v[i][j] > lef[i])lef[i] = ra.v[i][j],lc[i] = ra.a[i];

	for(register int i = 0;i < 3;++i)if(rb.a[i] != 0)

		for(register int j = 0;j < 3;++j)if(rb.b[j] != 0)

			if(rb.v[i][j] > rig[i])rig[i] = rb.v[i][j],rc[i] = rb.a[i];

	for(register int i = 0;i < 3;++i)if(lef[i] != 0)

		for(register int j = 0;j < 3;++j)if(rig[j] != 0)

			ans = max(ans,lef[i] + rig[j] - (lc[i] == rc[j]));

	return ans;

}

int main()

{

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	scanf("%d%d",&n,&m);

	register int a,b,c;

	for(register int i = 1;i <= m;++i)

	{

		a = read();b = read();c = read();

		if(a > b)swap(a,b);

		es[make_pair(a,b)].push_back(c);

	}

	for(register map<pair<int,int>,vector<int> >::iterator it = es.begin();it != es.end();++it)

	{

		sort(it -> se.begin(),it -> se.end());

		register vector<int>::iterator iter = unique(it -> se.begin(),it -> se.end());

		it -> se.erase(iter,it -> se.end());

		if(it -> se.size() > 3)it -> se.resize(3);

		add(it -> fi.fi,it -> fi.se,it -> se);

	}

	dep[1] = 1;

	dfs(1);

	for(register int i = 2;i <= n;++i)

	{

		for(register int it = 0;it < e[fae[i]].v.size();++it)

		{

			f[i][0].v[it][it] = 1;

			f[i][0].a[it] = e[fae[i]].v[it];

			f[i][0].b[it] = e[fae[i]].v[it];

			f[i][0].id = fa[i];

		}

	}

	for(register int i = 1;i <= 16;++i)

		for(register int k = 1;k <= n;++k)

			f[k][i] = merge(f[f[k][i - 1].id][i - 1],f[k][i - 1]);

	scanf("%d",&q);

	for(register int i = 1;i <= q;++i)

	{

		a = read();b = read();

		printf("%d\n",query(a,b));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}