<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

272. Evacuation plan
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(da, b) (a in A, b in B), where dista, 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.

Input
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.

Output
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.

Sample test(s)

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


Output
Test #1
1 1
1 3

Test #2
3 2
1 8 9
3 4 2
6 5 7
Author:	Michael R. Mirzayanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1. Abridged problem statement

We are given an undirected graph.

- Set `A`: important laboratories, each has one employee.
- Set `B`: laboratories with exits.
- `A` and `B` are disjoint.

An evacuation path must:

1. start from a vertex in `A`;
2. end at a vertex in `B`;
3. have length exactly

\[
K = \min_{a \in A, b \in B} dist(a,b)
\]

4. be vertex-disjoint from all other chosen paths, including starting and ending vertices.

We do **not** need the maximum possible number of paths. We only need output any evacuation plan that **cannot be extended** by adding another valid vertex-disjoint path of length `K`.

---

## 2. Key observations needed to solve the problem

### Observation 1: Compute distances from exits

Run a multi-source BFS from all vertices in `B`.

Let:

```text
dist[v] = shortest distance from v to any exit vertex in B
```

Then:

\[
K = \min_{a \in A} dist[a]
\]

The statement guarantees that at least one vertex from `A` can reach some exit, so `K` is finite.

---

### Observation 2: Only closest `A` vertices can start valid paths

A valid path must have length exactly `K`.

For an `A` vertex `a`:

- if `dist[a] > K`, then no exit is reachable from `a` in only `K` edges;
- if `dist[a] = K`, then shortest paths from `a` to exits have exactly the required length.

Since `K` is the minimum over all `A` vertices, no `A` vertex can have `dist[a] < K`.

Therefore, only vertices `a in A` with:

```text
dist[a] == K
```

can be starting vertices.

---

### Observation 3: Valid paths follow decreasing distances

Consider a shortest path from a usable `A` vertex to an exit.

If it starts at distance `K` and ends at distance `0`, and has exactly `K` edges, then every step must decrease `dist` by exactly `1`.

So every valid path has distance sequence:

```text
K, K - 1, K - 2, ..., 1, 0
```

Therefore, we can orient each tunnel `{u, v}` as a directed edge from the farther vertex to the closer vertex if their distances differ by exactly `1`.

That is:

```text
u -> v if dist[u] == dist[v] + 1
```

This gives a DAG of all shortest paths toward exits.

---

### Observation 4: Vertex-disjointness can be modeled with vertex splitting

We need paths that do not share vertices.

For each original vertex `v`, create two nodes:

```text
v_in
v_out
```

Add an edge:

```text
v_in -> v_out
```

with capacity `1`.

This ensures that at most one evacuation path can use vertex `v`.

For every directed shortest-path edge `u -> v`, add:

```text
u_out -> v_in
```

with capacity `1`.

Add:

- source edges to usable `A` vertices;
- sink edges from `B` vertices.

---

### Observation 5: We only need a maximal set, not a maximum set

The problem asks for a plan that cannot be extended.

This means we need a **maximal** set of disjoint valid paths: after choosing our paths, there should be no remaining unused valid path.

We do not need to reroute existing paths to get more paths.

Therefore, we can greedily find paths in the constructed network until no more source-to-sink path exists using unused capacity.

Because all capacities are `1` and the graph is acyclic, a DFS with current-edge pointers is enough.

---

## 3. Full solution approach based on the observations

### Step 1: Read the graph

Store:

- adjacency list for BFS;
- original edge list for building the shortest-path DAG.

Parallel edges are allowed and can be stored normally.

---

### Step 2: Multi-source BFS from all exits

Initialize:

```text
dist[b] = 0 for all b in B
```

Run BFS.

After BFS, `dist[v]` is the distance from `v` to the nearest exit.

Compute:

```text
K = min(dist[a]) over all a in A
```

---

### Step 3: Build auxiliary flow graph

Use vertex splitting.

For original vertex `v`:

```text
in(v) = v
out(v) = n + v
```

Use:

```text
source = 0
sink = 2 * n + 1
```

Add edges:

1. For every usable start `a in A` with `dist[a] == K`:

```text
source -> in(a)
```

capacity `1`.

2. For every vertex `v`:

```text
in(v) -> out(v)
```

capacity `1`.

3. For every original tunnel `{u, v}`:

If:

```text
dist[u] == dist[v] + 1
```

add:

```text
out(u) -> in(v)
```

If:

```text
dist[v] == dist[u] + 1
```

add:

```text
out(v) -> in(u)
```

capacity `1`.

4. For every exit `b in B`:

```text
out(b) -> sink
```

capacity `1`.

---

### Step 4: Greedily find paths

Repeatedly run DFS from `source` to `sink`.

If a DFS succeeds, mark all used edges on that path by increasing their flow.

Stop when no DFS can find another path.

Since we only use unused capacity and stop when no unused path remains, the selected paths form a non-extendable evacuation plan.

---

### Step 5: Reconstruct paths

Every used edge from `source` corresponds to one selected evacuation path.

Starting from the target `in(a)` of that edge:

1. output the current original vertex;
2. if `dist[current] == 0`, we reached an exit;
3. otherwise, move through the used edge from `out(current)` to the next `in(next)`.

Each reconstructed path has exactly `K + 1` vertices.

---

### Complexity

Multi-source BFS:

\[
O(N + M)
\]

Building the auxiliary graph:

\[
O(N + M)
\]

Greedy DFS phase:

\[
O(N + M)
\]

Total:

\[
O(N + M)
\]

Memory:

\[
O(N + M)
\]

This fits:

```text
N <= 10000
M <= 100000
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int cap;
    int flow;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<pair<int, int>> tunnels;

    tunnels.reserve(m);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        tunnels.push_back({u, v});

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int n1;
    cin >> n1;

    vector<int> A(n1);
    for (int i = 0; i < n1; i++) {
        cin >> A[i];
    }

    int n2;
    cin >> n2;

    vector<int> B(n2);
    for (int i = 0; i < n2; i++) {
        cin >> B[i];
    }

    const int INF = 1e9;

    /*
        Step 1:
        Multi-source BFS from all exits.

        dist[v] = shortest distance from v to any vertex in B.
    */
    vector<int> dist(n + 1, INF);
    queue<int> q;

    for (int b : B) {
        if (dist[b] == INF) {
            dist[b] = 0;
            q.push(b);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    /*
        Step 2:
        K is the minimum distance from any A-vertex to any exit.
    */
    int K = INF;

    for (int a : A) {
        K = min(K, dist[a]);
    }

    /*
        Auxiliary graph with vertex splitting.

        For every original vertex v:
            in(v)  = v
            out(v) = n + v

        source = 0
        sink   = 2 * n + 1
    */
    int source = 0;
    int sink = 2 * n + 1;
    int totalNodes = 2 * n + 2;

    auto inNode = [&](int v) {
        return v;
    };

    auto outNode = [&](int v) {
        return n + v;
    };

    vector<Edge> edges;
    vector<vector<int>> graph(totalNodes);

    auto addEdge = [&](int from, int to, int cap) {
        graph[from].push_back((int)edges.size());
        edges.push_back({to, cap, 0});
    };

    /*
        Source edges.

        Only A-vertices with dist[a] == K can start a valid path.
    */
    for (int a : A) {
        if (dist[a] == K) {
            addEdge(source, inNode(a), 1);
        }
    }

    /*
        Vertex capacity edges.

        Each original vertex may be used by at most one path.
    */
    for (int v = 1; v <= n; v++) {
        addEdge(inNode(v), outNode(v), 1);
    }

    /*
        Directed edges of the shortest-path DAG.

        A valid evacuation path always moves from distance d to d - 1.
    */
    for (auto [u, v] : tunnels) {
        if (dist[u] != INF && dist[u] == dist[v] + 1) {
            addEdge(outNode(u), inNode(v), 1);
        }

        if (dist[v] != INF && dist[v] == dist[u] + 1) {
            addEdge(outNode(v), inNode(u), 1);
        }
    }

    /*
        Exit edges.
    */
    for (int b : B) {
        addEdge(outNode(b), sink, 1);
    }

    /*
        Greedy DFS phase.

        ptr[u] remembers the first not-yet-useless outgoing edge of u.

        Since we only need a maximal set of paths, we do not need reverse edges
        and we do not need a full maximum flow algorithm.
    */
    vector<int> ptr(totalNodes, 0);

    function<bool(int)> dfs = [&](int u) -> bool {
        if (u == sink) {
            return true;
        }

        for (; ptr[u] < (int)graph[u].size(); ptr[u]++) {
            int id = graph[u][ptr[u]];
            Edge &e = edges[id];

            if (e.flow < e.cap && dfs(e.to)) {
                e.flow++;
                return true;
            }
        }

        return false;
    };

    while (dfs(source)) {
        // Keep adding paths while possible.
    }

    /*
        Reconstruct the chosen evacuation paths.

        Every used edge from source starts one path.
    */
    vector<vector<int>> paths;

    for (int id : graph[source]) {
        if (edges[id].flow == 0) {
            continue;
        }

        vector<int> path;

        // edges[id].to is inNode(a), which equals a in our numbering.
        int cur = edges[id].to;

        while (true) {
            path.push_back(cur);

            // dist == 0 means cur is an exit vertex.
            if (dist[cur] == 0) {
                break;
            }

            int nextVertex = -1;

            /*
                From out(cur), find the used edge going to the next vertex.
                Ignore possible edge to sink.
            */
            for (int eid : graph[outNode(cur)]) {
                Edge &e = edges[eid];

                if (e.flow == 1 && e.to != sink) {
                    nextVertex = e.to;
                    break;
                }
            }

            cur = nextVertex;
        }

        paths.push_back(path);
    }

    /*
        Output.
    */
    cout << paths.size() << ' ' << K << '\n';

    for (const auto &path : paths) {
        for (int i = 0; i < (int)path.size(); i++) {
            if (i) cout << ' ';
            cout << path[i];
        }
        cout << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from collections import deque


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    n = data[idx]
    idx += 1

    m = data[idx]
    idx += 1

    adj = [[] for _ in range(n + 1)]
    tunnels = []

    for _ in range(m):
        u = data[idx]
        idx += 1

        v = data[idx]
        idx += 1

        tunnels.append((u, v))

        adj[u].append(v)
        adj[v].append(u)

    n1 = data[idx]
    idx += 1

    A = data[idx:idx + n1]
    idx += n1

    n2 = data[idx]
    idx += 1

    B = data[idx:idx + n2]
    idx += n2

    INF = 10 ** 18

    # ------------------------------------------------------------
    # Step 1:
    # Multi-source BFS from all exits.
    #
    # dist[v] = shortest distance from v to any exit vertex.
    # ------------------------------------------------------------
    dist = [INF] * (n + 1)
    q = deque()

    for b in B:
        if dist[b] == INF:
            dist[b] = 0
            q.append(b)

    while q:
        u = q.popleft()

        for v in adj[u]:
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                q.append(v)

    # ------------------------------------------------------------
    # Step 2:
    # K is the shortest distance from set A to set B.
    # ------------------------------------------------------------
    K = min(dist[a] for a in A)

    # ------------------------------------------------------------
    # Auxiliary graph with vertex splitting.
    #
    # For every original vertex v:
    #     in_node(v)  = v
    #     out_node(v) = n + v
    #
    # source = 0
    # sink   = 2 * n + 1
    # ------------------------------------------------------------
    source = 0
    sink = 2 * n + 1
    total_nodes = 2 * n + 2

    def in_node(v):
        return v

    def out_node(v):
        return n + v

    # Each edge is represented as [to, capacity, flow].
    edges = []

    # graph[u] stores indices of outgoing edges from u.
    graph = [[] for _ in range(total_nodes)]

    def add_edge(u, v, cap):
        graph[u].append(len(edges))
        edges.append([v, cap, 0])

    # ------------------------------------------------------------
    # Source edges.
    #
    # Only A-vertices with dist[a] == K can start a valid path.
    # ------------------------------------------------------------
    for a in A:
        if dist[a] == K:
            add_edge(source, in_node(a), 1)

    # ------------------------------------------------------------
    # Vertex capacity edges.
    #
    # Each original vertex may be used by at most one path.
    # ------------------------------------------------------------
    for v in range(1, n + 1):
        add_edge(in_node(v), out_node(v), 1)

    # ------------------------------------------------------------
    # Directed shortest-path DAG edges.
    #
    # A valid path always goes from distance d to distance d - 1.
    # ------------------------------------------------------------
    for u, v in tunnels:
        if dist[u] != INF and dist[u] == dist[v] + 1:
            add_edge(out_node(u), in_node(v), 1)

        if dist[v] != INF and dist[v] == dist[u] + 1:
            add_edge(out_node(v), in_node(u), 1)

    # ------------------------------------------------------------
    # Exit edges.
    # ------------------------------------------------------------
    for b in B:
        add_edge(out_node(b), sink, 1)

    # ------------------------------------------------------------
    # Greedy DFS phase.
    #
    # We only need a maximal set of paths, not a maximum one.
    # Therefore, no reverse edges are needed.
    #
    # ptr[u] is the current outgoing edge pointer for node u.
    # ------------------------------------------------------------
    sys.setrecursionlimit(10 ** 6)

    ptr = [0] * total_nodes

    def dfs(u):
        if u == sink:
            return True

        while ptr[u] < len(graph[u]):
            eid = graph[u][ptr[u]]
            to, cap, flow = edges[eid]

            if flow < cap and dfs(to):
                edges[eid][2] += 1
                return True

            ptr[u] += 1

        return False

    while dfs(source):
        pass

    # ------------------------------------------------------------
    # Reconstruct the selected evacuation paths.
    #
    # Every used edge from source represents one chosen path.
    # ------------------------------------------------------------
    paths = []

    for eid in graph[source]:
        if edges[eid][2] == 0:
            continue

        path = []

        # edges[eid][0] is in_node(a), and in_node(a) == a.
        cur = edges[eid][0]

        while True:
            path.append(cur)

            # dist == 0 means this vertex is an exit.
            if dist[cur] == 0:
                break

            next_vertex = -1

            # Find the used edge from out_node(cur) to the next vertex.
            for out_eid in graph[out_node(cur)]:
                to, cap, flow = edges[out_eid]

                # Ignore the edge to sink.
                if flow == 1 and to != sink:
                    next_vertex = to
                    break

            cur = next_vertex

        paths.append(path)

    # ------------------------------------------------------------
    # Output.
    # ------------------------------------------------------------
    output = []
    output.append(f"{len(paths)} {K}")

    for path in paths:
        output.append(" ".join(map(str, path)))

    sys.stdout.write("\n".join(output))


if __name__ == "__main__":
    main()
```