1. Abridged Problem Statement
Given an N×N chessboard (1≤N≤40) with P removed cells, determine if the remaining cells can be fully covered by non-overlapping 2×1 dominoes placed on adjacent squares. If a tiling exists, output "Yes", then list the vertical dominoes (by the coordinates of their bottom cell) and the horizontal dominoes (by the coordinates of their left cell); otherwise, output "No".

2. Detailed Editorial
   Problem → Domino tiling on a grid with holes.
   Key fact: on a checkerboard coloring, any valid domino covers exactly one black and one white cell. A perfect tiling of all free cells thus corresponds one-to-one to a perfect matching in the bipartite graph whose vertices are free black and white cells and whose edges connect orthogonally adjacent free cells.

   Steps:
   1. Read N, P and mark removed cells on an N×N boolean board.
   2. Count free cells; if odd, immediately print "No".
   3. Partition free cells by color (parity of i+j). Number black cells from 0…B−1, white from 0…W−1.
   4. Build a bipartite graph: for each black cell, add an edge to each free white neighbor (up/down/left/right).
   5. Run Hopcroft–Karp to find maximum matching in O(E√V).
   6. If matched-edge count ×2 ≠ total free cells, tiling is impossible → "No".
   7. Otherwise extract each matched black–white pair as one domino, classify it as horizontal or vertical, normalize to its left or bottom square, and output the vertical list first then the horizontal list (each preceded by its count).

   Complexity:
   - V=O(N²)≤1600, E=O(4V), Hopcroft–Karp runs in O(E√V)≈O(N³) worst case, easily within time for N≤40.

3. C++ Solution
```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/hopcroft_karp.hpp>

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

class HopcroftKarp {
  private:
    int n, m;
    vector<int> dist;

    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for(int u = 0; u < n; u++) {
            if(inv_match[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }

        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                int m = match[v];
                if(m == -1) {
                    found = true;
                } else if(dist[m] == -1) {
                    dist[m] = dist[u] + 1;
                    q.push(m);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        for(int v: adj[u]) {
            int m = match[v];
            if(m == -1 || (dist[m] == dist[u] + 1 && dfs(m))) {
                inv_match[u] = v;
                match[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

  public:
    vector<int> match, inv_match;
    vector<vector<int>> adj;

    HopcroftKarp(int _n, int _m = -1) : n(_n), m(_m == -1 ? _n : _m) {
        adj.assign(n, vector<int>());
        clear(false);
    }

    void clear(bool clear_adj = true) {
        match.assign(m, -1);
        inv_match.assign(n, -1);
        if(clear_adj) {
            adj.assign(n, vector<int>());
        }
    }

    void add_edge(int u, int v) { adj[u].push_back(v); }

    int max_matching(bool shuffle_edges = false) {
        if(shuffle_edges) {
            for(int i = 0; i < n; i++) {
                shuffle(
                    adj[i].begin(), adj[i].end(),
                    mt19937(
                        chrono::steady_clock::now().time_since_epoch().count()
                    )
                );
            }
        }

        int ans = 0;
        while(bfs()) {
            for(int u = 0; u < n; u++) {
                if(inv_match[u] == -1 && dfs(u)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    vector<pair<int, int>> get_matching() {
        vector<pair<int, int>> matches;
        for(int u = 0; u < n; u++) {
            if(inv_match[u] != -1) {
                matches.emplace_back(u, inv_match[u]);
            }
        }
        return matches;
    }

    pair<vector<int>, vector<int>> minimum_vertex_cover() {
        vector<int> left_cover, right_cover;
        bfs();

        for(int u = 0; u < n; u++) {
            if(dist[u] == -1) {
                left_cover.push_back(u);
            }
        }

        for(int v = 0; v < m; v++) {
            if(match[v] != -1 && dist[match[v]] != -1) {
                right_cover.push_back(v);
            }
        }

        return {left_cover, right_cover};
    }
};

using BipartiteMatching = HopcroftKarp;

int n, p;
vector<pair<int, int>> removed;

void read() {
    cin >> n >> p;
    removed.resize(p);
    cin >> removed;
}

void solve() {
    // - Tiling the board with dominoes is a perfect matching on the grid graph
    //   where every remaining cell is a node and edges join orthogonally
    //   adjacent remaining cells. The grid is bipartite by colour (i + j)
    //   parity, so this is bipartite matching.
    //
    // - Build the bipartite graph with black cells on the left and white cells
    //   on the right, add an edge for each adjacent black/white pair, and run
    //   Hopcroft-Karp. A full tiling exists iff the total remaining cell count
    //   is even and the maximum matching covers all of them (2 * matching ==
    //   cells).
    //
    // - For the output, each matched pair is one domino: if the two cells share
    //   a row it is horizontal (report the left cell), otherwise vertical
    //   (report the bottom cell).

    vector<vector<bool>> board(n + 1, vector<bool>(n + 1, true));
    int total_cells = n * n;

    for(auto [x, y]: removed) {
        board[x][y] = false;
        total_cells--;
    }

    if(total_cells % 2 == 1) {
        cout << "No\n";
        return;
    }

    vector<pair<int, int>> black_cells, white_cells;
    map<pair<int, int>, int> black_id, white_id;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(!board[i][j]) {
                continue;
            }

            if((i + j) % 2 == 0) {
                black_id[{i, j}] = black_cells.size();
                black_cells.push_back({i, j});
            } else {
                white_id[{i, j}] = white_cells.size();
                white_cells.push_back({i, j});
            }
        }
    }

    BipartiteMatching bm(black_cells.size(), white_cells.size());

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    for(int i = 0; i < (int)black_cells.size(); i++) {
        auto [x, y] = black_cells[i];

        for(int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && board[nx][ny]) {
                if(white_id.count({nx, ny})) {
                    bm.add_edge(i, white_id[{nx, ny}]);
                }
            }
        }
    }

    int matching = bm.max_matching();
    if(matching * 2 != total_cells) {
        cout << "No\n";
        return;
    }

    cout << "Yes\n";
    vector<pair<int, int>> horizontal, vertical;
    for(int i = 0; i < (int)black_cells.size(); i++) {
        if(bm.inv_match[i] != -1) {
            auto [bx, by] = black_cells[i];
            auto [wx, wy] = white_cells[bm.inv_match[i]];

            if(bx == wx) {
                if(by < wy) {
                    horizontal.push_back({bx, by});
                } else {
                    horizontal.push_back({wx, wy});
                }
            } else {
                if(bx < wx) {
                    vertical.push_back({bx, by});
                } else {
                    vertical.push_back({wx, wy});
                }
            }
        }
    }

    cout << vertical.size() << "\n";
    for(auto [x, y]: vertical) {
        cout << x << " " << y << "\n";
    }

    cout << horizontal.size() << "\n";
    for(auto [x, y]: horizontal) {
        cout << x << " " << y << "\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution
```python
import sys
from collections import deque

def hopcroft_karp(adj, n_left, n_right):
    # adj: list of lists, adj[u] = neighbors v in [0..n_right)
    INF = 10**9
    pair_u = [-1]*n_left
    pair_v = [-1]*n_right
    dist = [0]*n_left

    def bfs():
        queue = deque()
        for u in range(n_left):
            if pair_u[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = INF
        found_augment = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                pu = pair_v[v]
                if pu == -1:
                    found_augment = True
                elif dist[pu] == INF:
                    dist[pu] = dist[u] + 1
                    queue.append(pu)
        return found_augment

    def dfs(u):
        for v in adj[u]:
            pu = pair_v[v]
            if pu == -1 or (dist[pu] == dist[u] + 1 and dfs(pu)):
                pair_u[u] = v
                pair_v[v] = u
                return True
        dist[u] = INF
        return False

    matching = 0
    while bfs():
        for u in range(n_left):
            if pair_u[u] == -1 and dfs(u):
                matching += 1
    return matching, pair_u, pair_v

def main():
    input_data = sys.stdin.read().strip().split()
    it = iter(input_data)
    n, p = map(int, (next(it), next(it)))
    removed = set()
    for _ in range(p):
        x, y = map(int, (next(it), next(it)))
        removed.add((x,y))

    # Build board of free cells
    total = n*n - p
    # If odd free cells, impossible
    if total % 2:
        print("No")
        return

    black, white = [], []
    bid, wid = {}, {}
    for i in range(1, n+1):
        for j in range(1, n+1):
            if (i,j) in removed: continue
            if (i+j) & 1 == 0:
                bid[(i,j)] = len(black)
                black.append((i,j))
            else:
                wid[(i,j)] = len(white)
                white.append((i,j))

    # Build adjacency from blacks to whites
    adj = [[] for _ in range(len(black))]
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    for u,(x,y) in enumerate(black):
        for dx,dy in dirs:
            vcoord = (x+dx, y+dy)
            if vcoord in wid:
                adj[u].append(wid[vcoord])

    # Run matching
    match_sz, pair_u, pair_v = hopcroft_karp(adj, len(black), len(white))
    if match_sz*2 != total:
        print("No")
        return

    print("Yes")
    horiz, vert = [], []
    # Each u matched to pair_u[u] ⇒ a domino
    for u,v in enumerate(pair_u):
        if v == -1: continue
        bx, by = black[u]
        wx, wy = white[v]
        if bx == wx:
            # horizontal: choose left cell
            if by < wy: horiz.append((bx,by))
            else:       horiz.append((wx,wy))
        else:
            # vertical: choose bottom cell
            if bx < wx: vert.append((bx,by))
            else:       vert.append((wx,wy))

    # Output vertical then horizontal (vertical count first)
    print(len(vert))
    for x,y in vert: print(x, y)
    print(len(horiz))
    for x,y in horiz: print(x, y)

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

5. Compressed Editorial
Color free cells checkerboard-style, build a bipartite graph between black and white free cells with edges for orthogonal adjacency, and check for a perfect matching via Hopcroft–Karp. If the matching covers all free cells, output the matched pairs as domino placements (vertical list first, then horizontal); otherwise print "No".
