<|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. In flow terms, a blocking flow.

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. With unit capacities every traversed edge is immediately saturated, so this naive DFS phase is already linear and the heavier MKM blocking-flow algorithm is unnecessary.

---

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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

struct edge {
    int to, cap, flow;
};

int n, m;
vector<vector<int>> adj;
vector<pair<int, int>> tunnels;
vector<int> a_set, b_set;

void read() {
    cin >> n >> m;
    adj.assign(n + 1, {});
    tunnels.resize(m);
    for(auto& [u, w]: tunnels) {
        cin >> u >> w;
        adj[u].push_back(w);
        adj[w].push_back(u);
    }
    int n1;
    cin >> n1;
    a_set.resize(n1);
    cin >> a_set;
    int n2;
    cin >> n2;
    b_set.resize(n2);
    cin >> b_set;
}

void solve() {
    // We need an unextendable family of vertex-disjoint shortest paths from the
    // A-labs to the B-labs, where every path has length K = min over a in A,
    // b in B of dist(a, b).
    //
    // A multi-source BFS from all B-labs gives dist[v] = distance to the
    // nearest exit, and K is the minimum dist over the A-labs. Only A-labs with
    // dist == K can host a path: a length-K shortest path visits vertices with
    // strictly decreasing distance K, K-1, ..., 0, so its start sits at
    // distance exactly K and its end at distance 0 (a B-lab). Consequently
    // A-labs only ever appear as starts and B-labs only as ends, so we never
    // have to treat them as interior vertices.
    //
    // The shortest-path DAG keeps an oriented edge u -> w whenever {u, w} is a
    // tunnel with dist[u] == dist[w] + 1 (one step closer to an exit). To
    // forbid sharing a lab we split every vertex into an in-node and an
    // out-node joined by a capacity-1 edge; a super source feeds the in-nodes
    // of the participating A-labs and the out-nodes of the B-labs feed a super
    // sink, all with capacity 1.
    //
    // A blocking flow in this layered unit-capacity network is exactly an
    // unextendable plan: it leaves no residual source-to-sink path along
    // forward edges, i.e. no further disjoint path can be added without
    // rerouting existing ones. We compute it with one greedy DFS phase using
    // current-arc pointers (a node that cannot reach the sink is skipped
    // permanently), then decompose the saturated edges into individual paths.
    //
    // The single blocking-flow phase is O(V + E). Every DFS step either fails
    // and advances a current-arc pointer, which happens at most once per edge
    // since pointers never move back, for O(E) total; or it succeeds and
    // retraces an augmenting path. Because all capacities are 1 and the splits
    // make the paths vertex-disjoint, every vertex lies on at most one path, so
    // the lengths of all augmenting paths sum to at most V. The BFS is also
    // O(V + E), so the whole solution is linear in the graph size.
    //
    // This is why the heavier MKM (Malhotra-Kumar-Maheshwari) blocking-flow
    // algorithm, O(V^2 + E), is not needed here: MKM pays off when capacities
    // are large and a single augmenting path can leave an edge partly used, so
    // current-arc DFS could revisit the same edge many times. With unit
    // capacities every traversed edge is immediately saturated, the naive DFS
    // phase is already O(V + E), and the extra machinery would only add cost.

    const int INF = INT_MAX;
    vector<int> dist(n + 1, INF);
    queue<int> bfs;
    for(int b: b_set) {
        if(dist[b] == INF) {
            dist[b] = 0;
            bfs.push(b);
        }
    }
    while(!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        for(int w: adj[u]) {
            if(dist[w] == INF) {
                dist[w] = dist[u] + 1;
                bfs.push(w);
            }
        }
    }

    int k = INF;
    for(int a: a_set) {
        k = min(k, dist[a]);
    }

    int src = 0, snk = 2 * n + 1;
    auto in_node = [&](int v) { return v; };
    auto out_node = [&](int v) { return n + v; };

    vector<edge> edges;
    vector<vector<int>> g(2 * n + 2);
    auto add_edge = [&](int u, int v, int cap) {
        g[u].push_back(edges.size());
        edges.push_back({v, cap, 0});
    };

    for(int a: a_set) {
        if(dist[a] == k) {
            add_edge(src, in_node(a), 1);
        }
    }
    for(int v = 1; v <= n; v++) {
        add_edge(in_node(v), out_node(v), 1);
    }
    for(auto& [u, w]: tunnels) {
        if(dist[u] != INF && dist[u] == dist[w] + 1) {
            add_edge(out_node(u), in_node(w), 1);
        } else if(dist[w] != INF && dist[w] == dist[u] + 1) {
            add_edge(out_node(w), in_node(u), 1);
        }
    }
    for(int b: b_set) {
        add_edge(out_node(b), snk, 1);
    }

    vector<int> ptr(2 * n + 2, 0);
    function<bool(int)> dfs = [&](int u) -> bool {
        if(u == snk) {
            return true;
        }
        for(; ptr[u] < (int)g[u].size(); ptr[u]++) {
            edge& e = edges[g[u][ptr[u]]];
            if(e.cap - e.flow > 0 && dfs(e.to)) {
                e.flow++;
                return true;
            }
        }
        return false;
    };

    while(dfs(src)) {
    }

    vector<vector<int>> paths;
    for(int id: g[src]) {
        if(edges[id].flow == 0) {
            continue;
        }
        vector<int> path;
        int cur = edges[id].to;
        while(true) {
            path.push_back(cur);
            if(dist[cur] == 0) {
                break;
            }
            for(int eid: g[out_node(cur)]) {
                if(edges[eid].flow == 1 && edges[eid].to != snk) {
                    cur = edges[eid].to;
                    break;
                }
            }
        }
        paths.push_back(path);
    }

    cout << paths.size() << ' ' << k << '\n';
    for(auto& path: paths) {
        cout << path << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation

```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()
```
