#nullable enable var stopwatch = new System.Diagnostics.Stopwatch(); stopwatch.Start(); var random = new Random(1); StreamReader _sr = new(Console.OpenStandardInput()); StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; const int N = 50; // const int K = 100; _sr.ReadLine(); var g = new int[N][]; for (var i = 0; i < N; i++) { var str = _sr.ReadLine()!; var row = new int[N]; for (var j = 0; j < N; j++) row[j] = str[j] - '0'; g[i] = row; } var ans = new List<(int, int)>(); void Run() { var h = new int[N][]; for (var i = 0; i < N; i++) { var rg = g[i]; var rh = new int[N]; for (var j = 0; j < N; j++) if (rg[j] >= 6) rh[j] = 1; h[i] = rh; } var score = int.MaxValue; while (stopwatch.ElapsedMilliseconds < 1900) { var iz = new int[N]; var jz = new int[N]; for (var lp = 0; lp < 2; lp++) { var x = iz[0] = random.Next(N); for (var i = 1; i < N; i++) { x = x + random.Next(2) - 1; x = Math.Max(Math.Min(x, N - 1), 0); iz[i] = x; } (iz, jz) = (jz, iz); } for (var i = 0; i < N; i++) h[i][jz[i]] ^= 2; for (var j = 0; j < N; j++) h[iz[j]][j] ^= 2; var uf = new UnionFind(N * N); for (var i = 0; i < N; i++) { var rh = h[i]; var t = i * N; for (var j = 0; j < N - 1; j++) { if (rh[j] != 1 || rh[j + 1] != 1) continue; uf.Union(t + j, t + j + 1); } } for (var i = 0; i < N - 1; i++) { var rh0 = h[i]; var rh1 = h[i + 1]; var t0 = i * N; var t1 = t0 + N; for (var j = 0; j < N; j++) { if (rh0[j] != 1 || rh1[j] != 1) continue; uf.Union(t0 + j, t1 + j); } } var s = 0; for (var i = 0; i < N; i++) { var rh = h[i]; var t = i * N; for (var j = 0; j < N; j++) { if (rh[j] != 1 || uf.Find(t + j) != t + j) continue; var c = uf.Size(t + j); s += c * c; } } if (s < score) { score = s; ans = []; for (var i = 0; i < N; i++) ans.Add((i, jz[i])); for (var j = 0; j < N; j++) ans.Add((iz[j], j)); } for (var i = 0; i < N; i++) h[i][jz[i]] ^= 2; for (var j = 0; j < N; j++) h[iz[j]][j] ^= 2; } } Run(); ans = [.. ans.Where(e => g[e.Item1][e.Item2] != 0).Distinct()]; _sw.WriteLine(ans.Count); foreach (var (ai, aj) in ans) _sw.WriteLine(ai + " " + aj); _sw.Flush(); class UnionFind { int[] Verticals { get; set; } public UnionFind(int verticals) { Verticals = new int[verticals]; Verticals.AsSpan().Fill(-1); } public int Union(int x, int y) { (x, y) = (Find(x), Find(y)); if (x == y) return x; var (sx, sy) = (Size(x), Size(y)); if (sx < sy) (x, y, sy) = (y, x, sx); Verticals[x] -= sy; return Verticals[y] = x; } public int Find(int x) { var p = Verticals[x]; if (p < 0) return x; return Verticals[x] = Find(p); } public int Size(int x) => -Verticals[Find(x)]; }