9572: 图之图

小 hua 发现了一个变幻莫测的图模型，边与边交织，图与图轮转。

小 hua 想知道在这个有向图中有多少条 $1$ 到 $n$ 的路径，结果对 109+7109+7 取模。

图由以下方式生成：

• 图共 $n$ 个节点，若干条边。
• 输入长度为 $n$ 的序列 aiai，每个 ai∈1,2,…,cai∈1,2,…,c。
• 再输入 $m$ 对无序数对 $u,v$。（可以出现 $u=v$）
• 图上的节点 i, j 之间存在有向边 i 到 j，当且仅当 i 小于 j，且 ai,ajai,aj 出现在输入的 m 对无序数对中。

注意：无序数对代表，设 $m=1$ 且输入的是 $1,2$ 且 a1=2,a2=1a1=2,a2=1，则图中是存在 $1\to 2$ 的边的。

第一行一个正整数 $T$ 表示测试点个数。

对于每组数据：

第一行两个正整数 $n,c$，分别表示图的节点数和序列值域限制。

第二行 $n$ 个正整数，即数列 aiai。

第三行一个正整数 $m$。

后面 $m$ 行每行两个正整数 ui,viui,vi，表示一个无序数对，保证每对无序数对不会重复出现。

本题输入量较大，请采用较快的输入方式。

对于所有数据，1≤T≤5,1≤n,c≤105,1≤m≤2×1051≤T≤5,1≤n,c≤105,1≤m≤2×105，1≤ai,ui,vi≤c1≤ai,ui,vi≤c。