题目描述

有一张 $n$ 个点 $m$ 条边的有向图，其中有 $a$ 个点可以作为起点，$b$ 个点可以作为终点，结点从 $1$ 到 $n$ 编号。

你可以任意选择若干条以某个起点走到某个终点的路径使得图上的每个点被经过至少一次。

求出最少需要的路径数量或报告无解。

输入格式

多测。第一行一个整数 $T$ 表示数据组数，对于每组数据，格式如下：

第一行四个正整数 $n,m,a,b$。

第二行 $a$ 个整数表示可以作为起点的点的编号。

第二行 $b$ 个整数表示可以作为终点的点的编号。

接下来 $m$ 行，每行两个整数 $u,v$ 表示一条边 $u\to v$。

输出格式

共 $T$ 行，每行一个整数表示对应数据的答案，或一行 no solution 表示无解。

2
2 1 1 1
1
2
2 1
3 2 3 3
1 2 3
1 2 3
1 2
1 3

no solution
2

数据规模与约定

对于 $30\%$ 的数据，$n\leq 10$，$m\leq 100$。

对于 $60\%$ 的数据，$n\leq 200$，$m\leq 5\times 10^3$。

对于 $100\%$ 的数据，$1\leq T\leq 10$，$1\leq a,b\leq n\leq 10^3$，$1\leq m\leq 10^4$。