// ─────────────────────────────────────────────────────────────────────────────
// POST-MORTEM: MAKE ALL DEGREES EVEN BY ADDING <= 2 EDGES   (Handshake AI / CodeSignal, Oct 2026)
// ─────────────────────────────────────────────────────────────────────────────
// TASK   : Undirected simple graph as an adjacency matrix (bool[][] or 0/1, n <= 50,
//          symmetric, diagonal false). Can you add at most two edges (no multi-edges,
//          no self-loops) so every vertex has even degree?
// KEY    : It's a PARITY problem. An edge (u, v) flips the parity of exactly u and v.
//          Handshake lemma -> the count of odd-degree vertices is always even.
//          Two edges flip at most 4 distinct vertices (a vertex hit twice nets to 0).
// CASES  : 0 odd -> true.  2 odd -> direct edge if free, else via a middle vertex w
//          adjacent to neither.  4 odd -> some perfect matching of the four using two
//          free edges.  6+ odd -> false.
// SAY    : "parity", "handshake lemma", "odd-degree vertices", "perfect matching",
//          "simple graph constraint", "O(n^2) to read the matrix, O(n) logic"
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

function canMakeAllDegreesEven(matrix) {
  const n = matrix.length;
  const odd = [];
  for (let i = 0; i < n; i++) {
    const degree = matrix[i].reduce((s, x) => s + x, 0);   // + coerces: true + true === 2
    if (degree % 2 === 1) odd.push(i);
  }

  if (odd.length === 0) return true;
  if (odd.length > 4) return false;                   // 2 edges can fix at most 4 parities

  // May we add edge u-v?  Use falsy, not `=== 0`: the harness may hand you booleans, and
  // `false === 0` is false.
  const free = (u, v) => u !== v && !matrix[u][v];

  if (odd.length === 2) {
    const [u, v] = odd;
    if (free(u, v)) return true;                      // one edge
    for (let w = 0; w < n; w++) {                     // two edges through a middle vertex
      if (free(u, w) && free(w, v)) return true;      // w flips twice -> stays even
    }
    return false;
  }

  const [a, b, c, d] = odd;                           // exactly 4 odd: need a perfect matching
  return (free(a, b) && free(c, d))
      || (free(a, c) && free(b, d))
      || (free(a, d) && free(b, c));
}

// ─────────────────────────────────────────────────────────────────────────────
// TEST HARNESS — each case is named after the branch of logic it exercises.
// To debug your own version: paste it below as `mine`, uncomment the runTests(mine)
// line, run `node post-mortems/even-degrees-with-two-edges.js`. The first FAIL line
// tells you which branch is missing or wrong.
// ─────────────────────────────────────────────────────────────────────────────
const graph = (n, edges, on = true, off = false) => {
  const m = Array.from({ length: n }, () => new Array(n).fill(off));
  for (const [u, v] of edges) { m[u][v] = on; m[v][u] = on; }
  return m;
};
const K = n => graph(n, Array.from({ length: n }, (_, i) => Array.from({ length: n - i - 1 }, (_, j) => [i, i + j + 1])).flat());

const CASES = [
  // [ what it tests, matrix, expected ]
  ['0 odd: single vertex, no edges',                       graph(1, []), true],
  ['0 odd: 3 isolated vertices',                           graph(3, []), true],
  ['0 odd: triangle (all degree 2)',                       graph(3, [[0, 1], [1, 2], [2, 0]]), true],
  ['0 odd: K5 (all degree 4)',                             K(5), true],

  ['2 odd: path of 4, ends not adjacent -> add 1 edge',    graph(4, [[0, 1], [1, 2], [2, 3]]), true],
  ['2 odd: single edge on 2 vertices, no middle vertex',   graph(2, [[0, 1]]), false],
  ['2 odd: edge exists, free middle vertex -> add 2 edges', graph(3, [[0, 1]]), true],
  ['2 odd: edge exists, every middle vertex blocked (K4 minus 0-1)', graph(4, [[0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]), false],
  ['2 odd: edge exists, every middle vertex free on ONE side only', graph(4, [[0, 1], [1, 2], [2, 3], [1, 3]]), false],   // odd {0,1}; 2 and 3 both touch 1
  ['2 odd: edge exists, only the LAST vertex works as middle', graph(5, [[0, 1], [0, 2], [1, 2], [0, 3], [1, 3]]), true],

  ['4 odd: two disjoint edges -> cross-match them',        graph(4, [[0, 1], [2, 3]]), true],
  ['4 odd: star K1,3 -> every pairing hits an existing edge', graph(4, [[0, 1], [0, 2], [0, 3]]), false],
  ['4 odd: K4 -> nothing free',                            K(4), false],
  ['4 odd: plus an even bystander vertex',                 graph(5, [[0, 1], [2, 3]]), true],
  ['4 odd: only the third pairing (a,d)+(b,c) is free',    graph(5, [[0, 1], [0, 2], [0, 4], [3, 4]]), true],   // odd {0,1,2,3}; 0-1 and 0-2 taken, 0-3 and 1-2 free

  ['6 odd: three disjoint edges',                          graph(6, [[0, 1], [2, 3], [4, 5]]), false],
  ['6 odd: K3,3 (all degree 3)',                           graph(6, [[0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]]), false],

  ['input as 0/1 numbers instead of booleans',             graph(3, [[0, 1]], 1, 0), true],
  ['input as 0/1 numbers, 4 odd star',                     graph(4, [[0, 1], [0, 2], [0, 3]], 1, 0), false],
];

function runTests(fn, label = fn.name || 'fn') {
  let failed = 0;
  for (const [name, m, expected] of CASES) {
    const got = fn(m.map(row => row.slice()));         // copy so a mutating solution can't poison later cases
    if (got !== expected) {
      failed++;
      console.log(`FAIL [${label}] ${name}\n     expected ${expected}, got ${got}\n     matrix: ${JSON.stringify(m.map(r => r.map(Number)))}`);
    }
  }
  return failed;
}

assert.equal(runTests(canMakeAllDegreesEven), 0);

// ── Paste your version here and uncomment the next line:
// function mine(matrix) { /* ... */ }
// if (runTests(mine) === 0) console.log('mine: all cases pass');

console.log('ok: post-mortems/even-degrees-with-two-edges.js');