Untitled

#include <climits>
#include <ios>
#include <iostream>
#include <queue>
#include <vector>

static constexpr int MAX_ROW = 110;
static constexpr int MAX_COL = 110;
static constexpr int MAX_NODES = MAX_ROW * MAX_COL;
static constexpr int INF = INT_MAX;

inline int to_in_id(int i, int j, int n, int m) { return i * m + j; }

inline int to_out_id(int i, int j, int n, int m) { return i * m + j + n * m; }

struct edge_type {
  int from;
  int to;
  long long capacity;
  long long flow{0};

  int x{-1};
  int y{-1};

  int reverse_edge{-1};
  bool reverse{true};

  edge_type(int from, int to, long long capacity)
      : from(from), to(to), capacity(capacity) {}

  edge_type(int from, int to, long long capacity, int x, int y)
      : from(from), to(to), capacity(capacity), x(x), y(y), reverse(false) {}
};

struct graph_type {
  int s;
  int t;
  std::vector<std::vector<edge_type>> edges;
  std::vector<int> distance;
  std::vector<int> path;
  std::queue<int> queue;

  graph_type(int s, int t)
      : s(s), t(t), edges(MAX_NODES, std::vector<edge_type>()),
        distance(MAX_NODES, -1), path(MAX_NODES, 0) {}

  void add_edge(int from, int to, long long capacity) {
    edges[from].emplace_back(from, to, capacity);
    edges[to].emplace_back(to, from, 0);

    edges[to].back().reverse_edge = edges[from].size() - 1;
    edges[from].back().reverse_edge = edges[to].size() - 1;
  }

  void add_edge(int from, int to, long long capacity, int x, int y) {
    edges[from].emplace_back(from, to, capacity, x, y);
  }

  bool bfs() {
    std::fill(distance.begin(), distance.end(), -1);
    distance[s] = 0;
    queue.push(s);

    while (!queue.empty()) {
      int v = queue.front();
      queue.pop();

      for (auto &to : edges[v]) {
        if (distance[to.to] == -1 && to.flow < to.capacity) {
          distance[to.to] = distance[v] + 1;
          queue.push(to.to);
        }
      }
    }

    return distance[t] != -1;
  }

  long long dfs(int v, long long min_flow) {
    if (v == t) {
      return min_flow;
    }

    for (size_t i = path[v]; i < edges[v].size(); ++i) {
      auto &to = edges[v][i];

      if (to.flow < to.capacity && distance[to.to] == distance[v] + 1) {
        long long flow = dfs(to.to, std::min(min_flow, to.capacity - to.flow));

        if (flow) {
          to.flow += flow;

          if (to.reverse_edge != -1) {
            edges[to.to][to.reverse_edge].flow -= flow;
          }

          return flow;
        }
      }

      path[v] = i + 1;
    }
    return 0;
  }

  long long max_flow() {
    long long flow = 0;

    while (bfs()) {
      std::fill(path.begin(), path.end(), 0);

      while (true) {
        long long pushed_flow = dfs(s, INF);
        flow += pushed_flow;

        if (!pushed_flow) {
          break;
        }
      }
    }

    return flow;
  }

  void dfs(int v, std::vector<bool> &visited, std::vector<int> &reached) {
    visited[v] = true;
    reached.push_back(v);

    for (const auto &edge : edges[v]) {
      if (!visited[edge.to]) {
        if (edge.flow < edge.capacity) {
          dfs(edge.to, visited, reached);
        }
      }
    }
  }

  int min_cut(std::vector<std::pair<int, int>> &coordinates) {
    std::vector<bool> visited(MAX_NODES, false);
    std::vector<int> reached;
    reached.reserve(MAX_NODES);

    dfs(s, visited, reached);
    int res = 0;

    for (int v : reached) {
      for (const auto &edge : edges[v]) {
        if (!visited[edge.to] && edge.flow == 1) {
          coordinates.emplace_back(edge.x, edge.y);
          ++res;
          break;
        }
      }
    }

    return res;
  }
};

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

  int n, m;
  std::cin >> n >> m;

  std::vector<std::string> data(n, std::string(m, '-'));

  int t, k;
  std::cin >> k;
  std::cin >> t;

  int row, col;
  for (int i = 0; i < k; ++i) {
    std::cin >> row;
    std::cin >> col;
    data[row - 1][col - 1] = '#';
  }

  for (int i = 0; i < t; ++i) {
    std::cin >> row;
    std::cin >> col;
    data[row - 1][col - 1] = '.';
  }

  int source, sink;

  std::cin >> row;
  std::cin >> col;
  data[row - 1][col - 1] = 'A';
  source = to_out_id(row - 1, col - 1, n, m);

  std::cin >> row;
  std::cin >> col;
  data[row - 1][col - 1] = 'B';
  sink = to_in_id(row - 1, col - 1, n, m);

  graph_type graph(source, sink);

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      switch (data[i][j]) {
      case '-':
        graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), INF, i, j);
        break;
      case '.':
        graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), 1, i, j);
        break;
      case '#':
        graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), 0, i, j);
        break;
      }
    }
  }

  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m - 1; ++j) {
      graph.add_edge(to_out_id(i, j, n, m), to_in_id(i + 1, j, n, m), INF);
      graph.add_edge(to_out_id(i + 1, j, n, m), to_in_id(i, j, n, m), INF);
      graph.add_edge(to_out_id(i, j, n, m), to_in_id(i, j + 1, n, m), INF);
      graph.add_edge(to_out_id(i, j + 1, n, m), to_in_id(i, j, n, m), INF);
    }
  }

  for (int i = 0; i < n - 1; ++i) {
    graph.add_edge(to_out_id(i, m - 1, n, m), to_in_id(i + 1, m - 1, n, m),
                   INF);
    graph.add_edge(to_out_id(i + 1, m - 1, n, m), to_in_id(i, m - 1, n, m),
                   INF);
  }

  for (int j = 0; j < m - 1; ++j) {
    graph.add_edge(to_out_id(n - 1, j, n, m), to_in_id(n - 1, j + 1, n, m),
                   INF);
    graph.add_edge(to_out_id(n - 1, j + 1, n, m), to_in_id(n - 1, j, n, m),
                   INF);
  }

  auto max_flow = graph.max_flow();

  if (max_flow >= INF) {
    std::cout << "-1\n";
    return 0;
  }

  std::vector<std::pair<int, int>> coordinates;
  coordinates.reserve(MAX_NODES);

  std::cout << graph.min_cut(coordinates) << "\n";

  for (size_t i = 0; i < coordinates.size(); ++i) {
    std::cout << (coordinates[i].first + 1) << " "
              << (coordinates[i].second + 1) << "\n";
  }

  return 0;
}