题目描述

某工厂由 $N$ 个实验室和 $M$ 条双向隧道组成。部分实验室属于重要部门，构成集合 $A$，每个这样的实验室中有一名员工；另一些实验室有通往建筑外的出口，构成集合 $B$。保证 $A\cap B=\varnothing$。

一份疏散方案包含若干条路径，并须满足：

• 每条路径从集合 $A$ 中的某个实验室出发，在集合 $B$ 中的某个实验室结束；
• 所有路径长度相同，且都等于集合 $A$ 到集合 $B$ 的最短距离 $K=\min_{a\in A,b\in B}\operatorname{dist}(a,b)$，路径长度按经过的隧道数计算；
• 任意两条路径不能共用实验室，包括起点和终点。

不要求让尽量多的员工参与，也不要求人数达到最大值；但输出方案必须是极大的：保持已有路径不变时，不能再加入一条或多条同样满足条件且与已有路径点不交的路径。

请构造任意一份这样的疏散方案。

输入格式

第一行包含两个整数 $N,M$。接下来 $M$ 行，每行两个整数 $u,v$，表示实验室 $u$ 与 $v$ 之间有一条双向隧道，同一对实验室之间可能有多条隧道。

随后一个整数 $N_1$，接下来给出 $N_1$ 个互不相同的实验室编号，构成集合 $A$。再随后一个整数 $N_2$，接下来给出 $N_2$ 个互不相同的实验室编号，构成集合 $B$。

保证至少存在一对 $a\in A,b\in B$，使 $a$ 可以到达 $b$；但并不保证每个 $A$ 中的实验室都能到达出口。

输出格式

第一行输出两个整数 $P,K$，其中 $P$ 是方案中的路径数，$K$ 是集合 $A$ 到集合 $B$ 的最短距离。

接下来 $P$ 行，每行输出 $K+1$ 个实验室编号，依次表示一条疏散路径。

若有多种合法且不可扩展的方案，可以输出任意一种。

数据范围

• $1\le N\le10000$
• $1\le M\le100000$
• $1\le N_1,N_2\le N$
• 时间限制：$0.25$ 秒
• 内存限制：$64$ MiB

样例 1

输入

4 3
1 4
1 3
2 3
2
1 2
2
3 4

输出

1 1
1 3

样例 2

输入

9 8
1 4
1 8
9 8
2 4
4 3
3 5
5 7
5 6
3
1 3 6
3
9 2 7

输出

3 2
1 8 9
3 4 2
6 5 7