## 1. Abridged problem statement

Given an undirected graph of laboratories and tunnels, two disjoint sets of vertices are specified:

- `A`: important labs, each containing one employee;
- `B`: labs with exits.

An evacuation path must start at a vertex in `A`, end at a vertex in `B`, and have length exactly

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

All chosen paths must be vertex-disjoint, including their starting and ending vertices.

It is not necessary to evacuate every employee. We only need output any evacuation plan that **cannot be extended** by adding another valid vertex-disjoint path of length `K`.



## 2. Detailed Editorial

### Key observation

Let `dist[v]` be the distance from vertex `v` to the nearest exit vertex in `B`.

We can compute all `dist[v]` with one multi-source BFS starting from every vertex in `B`.

Then

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

Only vertices `a in A` with `dist[a] = K` can be starting points of valid evacuation paths.

Why?

- A valid path must have length exactly `K`.
- The shortest distance from `a` to any exit is `dist[a]`.
- Since `K` is the minimum over all `A` vertices, no `A` vertex can have `dist[a] < K`.
- If `dist[a] > K`, it is impossible to reach an exit in only `K` steps.
- Therefore only `A` vertices with `dist[a] = K` may participate.

Now consider a shortest path from such an `A` vertex to a `B` vertex. Along that path, the distance to the nearest exit decreases by exactly `1` at every step:

\[
K, K-1, K-2, \dots, 0
\]

So we can orient every tunnel `{u, v}` from the vertex with larger `dist` to the vertex with smaller `dist`, but only if their distances differ by exactly `1`.

That gives a directed acyclic graph of all shortest paths toward exits. Notice that A-labs always appear at distance exactly `K` (only as starts) and B-labs at distance `0` (only as ends), so they never need to be treated as interior vertices.

---

### Enforcing vertex-disjointness

We need paths that do not share vertices.

A standard trick is vertex splitting:

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

- `v_in`
- `v_out`

Add an edge:

```text
v_in -> v_out
```

with capacity `1`.

This means at most one evacuation path can pass through vertex `v`.

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

```text
u_out -> v_in
```

with capacity `1`.

Add a super source `S` and a super sink `T`.

For every usable starting vertex `a in A` with `dist[a] = K`, add:

```text
S -> a_in
```

with capacity `1`.

For every exit vertex `b in B`, add:

```text
b_out -> T
```

with capacity `1`.

Now every unit flow from `S` to `T` corresponds to one valid evacuation path.

---

### Why a maximum flow is not necessary

The problem does not require the maximum possible number of paths.

It only requires a plan that cannot be extended by simply adding one more valid disjoint path.

So it is enough to build a **maximal** set of vertex-disjoint shortest paths, i.e. a blocking flow: a flow that leaves no residual source-to-sink path along forward edges, so no further disjoint path can be added without rerouting existing ones.

The provided solution does this using one DFS-based blocking-flow phase without reverse edges.

Each DFS tries to find one more path from `S` to `T`.

Once a vertex/edge is saturated, it cannot be used again.

The `ptr` array stores the current outgoing edge tried for each node. If an outgoing edge fails to lead to the sink, the algorithm never tries it again.

When no DFS from `S` succeeds anymore, there is no unused directed path from a valid source to an exit in the remaining graph. Therefore the current plan cannot be extended.

This is also 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 linear, and the extra machinery would only add cost.

---

### Complexity

Multi-source BFS:

\[
O(N + M)
\]

Building the flow graph:

\[
O(N + M)
\]

The greedy blocking-flow DFS phase is also linear in this unit-capacity setting:

\[
O(N + M)
\]

Total complexity:

\[
O(N + M)
\]

Memory complexity:

\[
O(N + M)
\]

This fits the constraints:

- `N <= 10000`
- `M <= 100000`



## 3. C++ Solution

```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;
}
```



## 4. Python Solution

```python
import sys
from collections import deque


def main():
    # Read all integers from standard input at once for speed.
    data = list(map(int, sys.stdin.buffer.read().split()))

    # Pointer into the input array.
    idx = 0

    # Read number of vertices and tunnels.
    n = data[idx]
    idx += 1
    m = data[idx]
    idx += 1

    # Original undirected graph adjacency list.
    # Vertices are numbered from 1 to n.
    adj = [[] for _ in range(n + 1)]

    # Store the original tunnel list as pairs.
    tunnels = []

    # Read all tunnels.
    for _ in range(m):
        u = data[idx]
        idx += 1
        v = data[idx]
        idx += 1

        tunnels.append((u, v))

        # Undirected graph: add both directions.
        adj[u].append(v)
        adj[v].append(u)

    # Read set A.
    n1 = data[idx]
    idx += 1
    a_set = data[idx:idx + n1]
    idx += n1

    # Read set B.
    n2 = data[idx]
    idx += 1
    b_set = data[idx:idx + n2]
    idx += n2

    # Large value representing infinity.
    INF = 10 ** 18

    # dist[v] = distance from v to nearest exit in B.
    dist = [INF] * (n + 1)

    # Multi-source BFS queue.
    q = deque()

    # Initialize BFS with all exits.
    for b in b_set:
        if dist[b] == INF:
            dist[b] = 0
            q.append(b)

    # Standard BFS.
    while q:
        u = q.popleft()

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

    # K is the shortest distance from any A-lab to any B-lab.
    k = min(dist[a] for a in a_set)

    # Node ids in the auxiliary split graph:
    # source = 0
    # in_node(v) = v
    # out_node(v) = n + v
    # sink = 2 * n + 1
    src = 0
    snk = 2 * n + 1
    total_nodes = 2 * n + 2

    def in_node(v):
        # Input side of original vertex v.
        return v

    def out_node(v):
        # Output side of original vertex v.
        return n + v

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

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

    def add_edge(u, v, cap):
        # Add edge index to adjacency list.
        g[u].append(len(edges))

        # Store directed edge.
        edges.append([v, cap, 0])

    # Add source edges to usable A-labs.
    # Only A-labs with dist[a] == k can start a length-k shortest path.
    for a in a_set:
        if dist[a] == k:
            add_edge(src, in_node(a), 1)

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

    # Add directed edges along shortest paths toward exits.
    for u, v in tunnels:
        # If u is exactly one step farther from exits than v,
        # then a shortest path may go u -> v.
        if dist[u] != INF and dist[u] == dist[v] + 1:
            add_edge(out_node(u), in_node(v), 1)

        # If v is exactly one step farther from exits than u,
        # then a shortest path may go v -> u.
        elif dist[v] != INF and dist[v] == dist[u] + 1:
            add_edge(out_node(v), in_node(u), 1)

    # Add exit edges to sink.
    for b in b_set:
        add_edge(out_node(b), snk, 1)

    # Current edge pointer for each auxiliary node.
    ptr = [0] * total_nodes

    # Recursion depth may be up to the path length in the split graph.
    sys.setrecursionlimit(10 ** 6)

    def dfs(u):
        """
        Try to find one more available path from u to the sink.

        This is a greedy DFS with current-arc optimization.
        It does not use reverse edges because we only need a maximal,
        not maximum, set of paths.
        """

        # Sink reached: path found.
        if u == snk:
            return True

        # Try outgoing edges starting from the saved pointer.
        while ptr[u] < len(g[u]):
            eid = g[u][ptr[u]]
            to, cap, flow = edges[eid]

            # If this edge has remaining capacity and the destination
            # can reach the sink, use this edge.
            if cap - flow > 0 and dfs(to):
                edges[eid][2] += 1
                return True

            # This edge cannot help anymore; skip it forever.
            ptr[u] += 1

        # No outgoing edge leads to the sink.
        return False

    # Repeatedly add one more path while possible.
    while dfs(src):
        pass

    # Reconstruct actual paths from saturated source edges.
    paths = []

    for eid in g[src]:
        # Only used source edges correspond to selected evacuation paths.
        if edges[eid][2] == 0:
            continue

        # The target of source edge is a_in.
        # Since in_node(a) == a, it is also the original vertex number.
        cur = edges[eid][0]

        path = []

        while True:
            # Add current original vertex.
            path.append(cur)

            # dist == 0 means this vertex is in B, so path ends here.
            if dist[cur] == 0:
                break

            # Move along the unique saturated shortest-path edge from cur.
            next_cur = None

            for out_eid in g[out_node(cur)]:
                to, cap, flow = edges[out_eid]

                # Ignore edge to sink; we only want movement to next lab.
                if flow == 1 and to != snk:
                    next_cur = to
                    break

            # This should always exist for a valid saturated path.
            cur = next_cur

        # Store reconstructed path.
        paths.append(path)

    # Prepare output.
    output = []

    # First line: number of paths and common length.
    output.append(f"{len(paths)} {k}")

    # Each path contains k + 1 vertices.
    for path in paths:
        output.append(" ".join(map(str, path)))

    # Print final answer.
    sys.stdout.write("\n".join(output))


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



## 5. Compressed Editorial

Run multi-source BFS from all exits `B`, obtaining `dist[v]`, the distance from each vertex to the nearest exit.

Let:

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

Only `A` vertices with `dist[a] = K` can start valid paths.

Build the shortest-path DAG by orienting each tunnel `{u,v}` from the vertex with larger distance to the one with smaller distance if the distances differ by exactly `1`.

To enforce vertex-disjoint paths, split every vertex `v` into `v_in -> v_out` with capacity `1`. Add edges:

- `source -> a_in` for every `a in A` with `dist[a] = K`;
- `u_out -> v_in` for each oriented shortest-path edge `u -> v`;
- `b_out -> sink` for every `b in B`.

Now every unit path from source to sink is a valid evacuation route of length `K`.

Since the task asks only for a non-extendable plan, not a maximum one, greedily find paths using DFS with current-edge pointers until no more path exists. The resulting set is maximal (a blocking flow), so it cannot be extended.

Finally, decompose saturated edges into original vertex paths and print them.

Complexity:

\[
O(N + M)
\]
