p272.ans1
======================
1 1
1 3

=================
p272.in2
======================
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

=================
p272.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;
}

=================
p272.ans2
======================
3 2
1 8 9
3 4 2
6 5 7

=================
p272.in1
======================
4 3
1 4
1 3
2 3
2
1 2
2
3 4

=================
statement.txt
======================
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

=================
