给定两张 \(n_1/n_2\) 个点 \(m_1/m_2\) 条边的有向图 \(G_1,G_2\)，每条边有一个小写字母。

定义字符串 \(S\) 和一条路径匹配当且仅当按顺序写下路径上边的字符，得到的字符串与 \(S\) 相同。

定义字符串 \(S\) 在一张图 \(G\) 的出现次数为 \(G\) 中与 \(S\) 匹配的路径数。

定义字符串 \(S\) 合法当且仅当 \(S\) 在 \(G_1,G_2\) 中的出现次数不相等。求最短的合法字符串 \(S\)，如果长度相同求字典序最小的，若不存在则判断无解。

\(n\le 500\)，\(m\le 3000\)。

---

题解说最短的合法串长度 \(\le n_1+n_2\)。

考虑统计串 \(s=s_1s_2\cdots s_L\) 在 \(G_1,G_2\) 中的出现次数之差：将两个图拼成 \(n_1+n_2\) 个点的大图 \(G\)，设 \(f_{k,v}\) 表示长度为 \(k\) 且与 \(s_1\cdots s_k\) 匹配且最后一个节点是 \(v\) 的路径数量。

这是线性递推，可以写成矩阵形式：设 \(26\) 个字符的邻接矩阵是 \(M_a,\cdots,M_z\)，\(u_I^{\top}\) 是元素均为 \(1\) 的行向量，\(u_O\) 是前 \(n_1\) 个元素为 \(1\)，后 \(n_2\) 个元素为 \(-1\) 的列向量，则串合法当且仅当 \(u_I^{\top}M_{s_1}\cdots M_{s_L}u_O\ne 0\)。

设 \(V_K\) 表示所有 \(L\le K\) 的字符串 \(s\) 对应的行向量 \(u_I^{\top}M_{s_1}M_{s_2}\cdots M_{s_L}\) 的集合，则最短的合法串长度 \(\le K\) 当且仅当 \(V_K\) 中有元素 \(u^{\top}\) 满足 \(u^{\top}u_O\ne 0\)。

设 \(U_K=\text{span}(V_K)\)，则又转化为 \(U_K\) 中有元素 \(u^{\top}\) 满足 \(u^{\top}u_O\ne 0\)。

对于行向量集合 \(V\) 和矩阵 \(M\)，设 \(VM=\{u^{\top}M:u\in V\}\)，则

\[V_K=V_{K-1}\cup\left(\bigcup_{c\in\Sigma}V_{K-1}M_c\right) \\ U_K=\text{span}\left(U_{K-1}\cup\left(\bigcup_{c\in\Sigma}U_{K-1}M_c\right)\right) \]

显然 \(U_1\sube U_2\sube\cdots\)，且因为它是一阶递推式，而维数 \(\le n_1+n_2\)，所以 \(U_{n_1+n_2}=U_{n_1+n_2+1}=\cdots\)，所以若 \(U_K\) 内有元素 \(u^{\top}u_O\ne 0\)，则最小的 \(K\le n_1+n_2\)，得证。

结果发现上面这一长串并不重要（

重点在于不会 fst 的 Hash 技巧：生成 \((n_1+n_2)|\Sigma|\) 个随机数，表示每个位置的每个字符的 Hash 值，字符串的 Hash 值是其所有字符 Hash 值乘积，字符串集合的 Hash 值是其所有字符串 Hash 值之和。

先把长度求出来，最后按位贪心即可，时间复杂度 \(O(nm|\Sigma|)\)。

只要不卡就可以随便自然溢出...吗？既然是算乘积那肯定只能用奇数。

#include<bits/stdc++.h>
#define PB emplace_back
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long u64;
const int N = 501;
template<typename T>
void rd(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
u64 val[26][N<<1];
int L, cr;
struct Graph {
	int n, le;
	u64 f[N][N<<1], g[N], h[N];
	vector<pii> E[N];
	Graph(){
		int m; rd(n); rd(m);
		while(m --){
			int u, v, c; rd(u); rd(v);
			do c = getchar(); while(c < 'a' || c > 'z');
			E[u].PB(v, c - 'a');
		}
		for(int i = 1;i <= n;++ i){
			f[i][0] = g[i] = 1; h[i] = 0;
		}
	}
	u64 work(){
		u64 res = 0;
		for(int i = 1;i <= n;++ i){
			for(pii _ : E[i])
				f[i][cr] += f[_.fi][cr-1] * val[_.se][cr];
			res += f[i][cr];
		} return res;
	}
	u64 calc(int c){
		u64 res = 0;
		for(int i = 1;i <= n;++ i)
			for(pii _ : E[i]) if(_.se == c)
				res += g[i] * val[c][cr-le] * f[_.fi][cr-le-1];
		return res;
	}
	void upd(int c){
		for(int i = 1;i <= n;++ i)
			for(pii _ : E[i]) if(_.se == c)
				h[_.fi] += g[i] * val[c][cr-le];
		memcpy(g, h, n+1<<3);
		memset(h, 0, n+1<<3); ++le;
	}
} G1, G2;
int main(){
	L = G1.n + G2.n;
	for(int i = 0;i < 26;++ i)
		for(int j = 1;j <= L;++ j)
			val[i][j] = rng() | 1;
	for(cr = 1;cr <= L;++ cr) if(G1.work() != G2.work()){
		for(int i = 1;i <= cr;++ i)
			for(int j = 0;j < 26;++ j) if(G1.calc(j) != G2.calc(j)){
				putchar(j + 'a'); G1.upd(j); G2.upd(j); break;
			}
		return 0;
	} puts("Same");
}