题目描述

给定一个$n$个点$m$条边的有向无环图，其中每条边$(u_i,v_i)$上有一个小写字母$c_i$，所有边都是从编号较小的节点指向编号较大的节点，定义一条路径生成的字符串为路径经过的边上字符的顺序拼接。

有$q$次询问，每次询问给定起点$S_i$和终点$T_i$，求从$S_i$到$T_i$的路径可以生成的字典序最小的字符串。

输入格式

第一行三个正整数$n,m, q$。

接下来$m$行，每行两个正整数$u_i,v_i$以及一个小写字母$c_i$，表示第$i$条边。

接下来$q$行，每行两个正整数$S_i,T_i$，表示路径的起点和终点。

输出格式

$q$行，每行一个字符串，第$i$行表示第$i$次询问的答案，若不存在$S_i$到$T_i$的路径，输出No Solution!。

样例

样例输入 #1

5 4 3
1 2 a
1 3 a
2 3 a
3 4 b
1 3
2 5
1 4

样例输出 #1

a
No Solution!
aab

数据范围

对于100%的数据：$1\le n\le 4000,1\le m\le\frac{n(n-1)}{2},1\le q\le 10^4,1\le u_i<v_i\le n,1\le S<T\le n,c_i\in\{\text{'a'},\text{'b'},\cdots,\text{'z'}\}$。

**注意：**子任务4中$m$的上限为$\frac{1000\times 999}{2}=499500$。

本题输入输出量较大，这里提供快读快输模板：

namespace nqio{const unsigned R=4e5,W=4e5;char*a,*b,i[R],o[W],*c=o,*d=o+W,h[40],*p=h,y;bool s;struct q{void r(char&x){x=a==b&&(b=(a=i)+fread(i,1,R,stdin),a==b)?-1:*a++;}void f(){fwrite(o,1,c-o,stdout);c=o;}~q(){f();}void w(char x){*c=x;if(++c==d)f();}q&operator>>(char&x){do r(x);while(x<=32);return*this;}q&operator>>(char*x){do r(*x);while(*x<=32);while(*x>32)r(*++x);*x=0;return*this;}template<typename t>q&operator>>(t&x){for(r(y),s=0;!isdigit(y);r(y))s|=y==45;if(s)for(x=0;isdigit(y);r(y))x=x*10-(y^48);else for(x=0;isdigit(y);r(y))x=x*10+(y^48);return*this;}q&operator<<(char x){w(x);return*this;}q&operator<<(char*x){while(*x)w(*x++);return*this;}q&operator<<(const char*x){while(*x)w(*x++);return*this;}template<typename t>q&operator<<(t x){if(!x)w(48);else if(x<0)for(w(45);x;x/=10)*p++=48|-(x%10);else for(;x;x/=10)*p++=48|x%10;while(p!=h)w(*--p);return*this;}}qio;}using nqio::qio;

使用时将cin和cout替换为qio即可。

**提示：**你的算法可能比你想象的要快。