time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard input
output: standard output

The main building of "Waste Production Berland's Factory" consists of a number of laboratories. Some pairs of the laboratories are connected with bidirectional tunnels. Secret research of waste recycling is carryed out in some of the laboratories. Those laboratories have the strategic importance. The set of such laboratories will be marked with letter A (or will call A-department). Let's mark the laboratories that have an exit from the building with letter B. No laboratory of the A-department has an exit outside due to its high importance (i.e. the intersection of the sets A and B is empty). There is one employee in each laboratory of A-department.
Due to the threat of a terrorist attack, the head of the A-department has to make the evacuation plan of his department employees. Modern security requirements demand the following rules to be obeyed:

- there should be a way to the laboratory with an exit from the factory (laboratory from the set B) for each employee participating in evacuation;

- all those ways should have equal lengths and this length should be equal to the length of the shortest path from the set A to the set B (path length is the number of the tunnels on the way between laboratories), i.e. all path lengths should be equal to min(d_{a, b}) (a in A, b in B), where dist_{a, b} is the length of the shortest path from laboratory a to laboratory b;

- no two ways should have a common laboratory (including the first and last laboratories of the way).

The factory owners do not require each employee to have such a way (sometimes it can be even impossible). However, if the owners find out that the evacuation plan can be extended with one or more paths, the whole department will loose the annual bonus. So, all department employees decided to take part in the plan preparation.
Obviously the plan with maximum possible number of ways will satisfy the owners. After several days of unsuccessful attempts to create such a plan the decision was made just to create a plan, which cannot be extended. However, this task also seems rather difficult. You are to help to find such a plan.

The first line of the input file contains two integer numbers N, M (1 <= N <= 10000; 1 <= M <= 100000), N -- the number of the laboratories, M -- the number of the tunnels. The following M lines contain the descriptions of the tunnels, the pairs of the laboratory numbers connected with the corresponding tunnel. The number N1 (1 <= N1 <= N) follows, it is the number of the laboratories in the A-department. The following N1 numbers designate the numbers of the laboratories of this department. The number N2 (1 <= N2 <= N) follows, it is the number of the laboratories in set B. The following N2 numbers describe the laboratories. It is possible that a pair of laboratories is connected with more than one tunnel. You can assume that it is possible to get from one of the laboratories of A-department to one of the exits, but it does not mean that it is possible for any A-department laboratory.

You should output evacuation plan which cannot be extended. You should output in the first line two integer numbers P and K, where P is the number of employees participating in the evacuation, K -- the length of the ways in the evacuation plan. Each of the following P lines should contain K+1 numbers, representing the evacuation plan of the corresponding employee. If there are several solutions, you can output any of them.

Input

Test #1
4 3
1 4
1 3
2 3
2
1 2
2
3 4

Test #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