← Home
For problem statement at 2000-2999/2000-2099/2060-2069/2061/problemG.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2060-2069/2061/verifierG.go ends with Accepted (50 tests). can you fix the verifier? ```go
package main

import (
	"bytes"
	"io"
	"math/bits"
	"os"
	"strconv"
)

type FastInput struct {
	data []byte
	idx  int
}

func NewFastInput() *FastInput {
	data, _ := io.ReadAll(os.Stdin)
	return &FastInput{data: data}
}

func (in *FastInput) skip() {
	for in.idx < len(in.data) && in.data[in.idx] <= ' ' {
		in.idx++
	}
}

func (in *FastInput) NextBytes() []byte {
	in.skip()
	start := in.idx
	for in.idx < len(in.data) && in.data[in.idx] > ' ' {
		in.idx++
	}
	return in.data[start:in.idx]
}

func (in *FastInput) NextInt() int {
	in.skip()
	v := 0
	for in.idx < len(in.data) && in.data[in.idx] > ' ' {
		v = v*10 + int(in.data[in.idx]-'0')
		in.idx++
	}
	return v
}

func parseIntBytes(b []byte) int {
	v := 0
	for _, c := range b {
		v = v*10 + int(c-'0')
	}
	return v
}

func firstInter(a, b []uint64) int {
	for i := 0; i < len(a); i++ {
		x := a[i] & b[i]
		if x != 0 {
			return i*64 + bits.TrailingZeros64(x)
		}
	}
	return -1
}

func firstInterExcl(a, b []uint64, excl int) int {
	ew := excl >> 6
	em := uint64(1) << (uint(excl) & 63)
	for i := 0; i < len(a); i++ {
		x := a[i] & b[i]
		if i == ew {
			x &^= em
		}
		if x != 0 {
			return i*64 + bits.TrailingZeros64(x)
		}
	}
	return -1
}

func clearBit(bs []uint64, v int) {
	bs[v>>6] &^= uint64(1) << (uint(v) & 63)
}

func main() {
	in := NewFastInput()
	first := in.NextBytes()
	if len(first) == 0 {
		return
	}

	var t int
	if string(first) == "manual" {
		t = in.NextInt()
	} else {
		t = parseIntBytes(first)
	}

	var out bytes.Buffer

	for ; t > 0; t-- {
		n := in.NextInt()
		s := in.NextBytes()
		k := (n + 1) / 3

		words := (n + 63) >> 6
		raw := make([]uint64, n*words)
		adj := make([][]uint64, n)
		for i := 0; i < n; i++ {
			adj[i] = raw[i*words : (i+1)*words]
		}

		mate := make([]int, n)
		for i := 0; i < n; i++ {
			mate[i] = -1
		}

		initEdges := make([][2]int, 0, n/2)

		p := 0
		for i := 0; i < n-1; i++ {
			rowi := adj[i]
			bitI := uint64(1) << (uint(i) & 63)
			for j := i + 1; j < n; j++ {
				if s[p] == '1' {
					rowi[j>>6] |= uint64(1) << (uint(j) & 63)
					adj[j][i>>6] |= bitI
					if mate[i] == -1 && mate[j] == -1 {
						mate[i] = j
						mate[j] = i
						initEdges = append(initEdges, [2]int{i, j})
					}
				}
				p++
			}
		}

		freeBits := make([]uint64, words)
		for i := 0; i < n; i++ {
			if mate[i] == -1 {
				freeBits[i>>6] |= uint64(1) << (uint(i) & 63)
			}
		}

		aug := 0
		for _, e := range initEdges {
			a, b := e[0], e[1]
			if mate[a] != b || mate[b] != a {
				continue
			}
			x1 := firstInter(adj[a], freeBits)
			if x1 == -1 {
				continue
			}
			y1 := firstInter(adj[b], freeBits)
			if y1 == -1 {
				continue
			}

			u, v := -1, -1
			if x1 != y1 {
				u, v = x1, y1
			} else {
				x2 := firstInterExcl(adj[a], freeBits, x1)
				if x2 != -1 {
					u, v = x2, y1
				} else {
					y2 := firstInterExcl(adj[b], freeBits, y1)
					if y2 != -1 {
						u, v = x1, y2
					} else {
						continue
					}
				}
			}

			mate[a] = u
			mate[u] = a
			mate[b] = v
			mate[v] = b
			clearBit(freeBits, u)
			clearBit(freeBits, v)
			aug++
		}

		m := len(initEdges) + aug
		ans := make([][2]int, 0, k)

		if m >= k {
			for i := 0; i < n && len(ans) < k; i++ {
				if mate[i] > i {
					ans = append(ans, [2]int{i + 1, mate[i] + 1})
				}
			}
		} else {
			finalFreeBits := make([]uint64, words)
			freeList := make([]int, 0, n-2*m)
			for i := 0; i < n; i++ {
				if mate[i] == -1 {
					finalFreeBits[i>>6] |= uint64(1) << (uint(i) & 63)
					freeList = append(freeList, i)
				}
			}

			for i := 0; i < n; i++ {
				j := mate[i]
				if j > i {
					chosen := -1
					blocked := -1

					fi := firstInter(adj[i], finalFreeBits)
					fj := firstInter(adj[j], finalFreeBits)

					if fi == -1 {
						chosen = i
					} else if fj == -1 {
						chosen = j
					} else {
						chosen = i
						blocked = fi
					}

					l := len(freeList)
					var u int
					if blocked == -1 || freeList[l-1] != blocked {
						u = freeList[l-1]
						freeList = freeList[:l-1]
					} else {
						u = freeList[l-2]
						freeList[l-2] = freeList[l-1]
						freeList = freeList[:l-1]
					}

					clearBit(finalFreeBits, u)
					ans = append(ans, [2]int{chosen + 1, u + 1})
				}
			}

			for len(ans) < k {
				a := freeList[len(freeList)-1]
				b := freeList[len(freeList)-2]
				freeList = freeList[:len(freeList)-2]
				ans = append(ans, [2]int{a + 1, b + 1})
			}
		}

		out.WriteString(strconv.Itoa(k))
		out.WriteByte('\n')
		for i, p := range ans {
			if i > 0 {
				out.WriteByte(' ')
			}
			out.WriteString(strconv.Itoa(p[0]))
			out.WriteByte(' ')
			out.WriteString(strconv.Itoa(p[1]))
		}
		out.WriteByte('\n')
	}

	os.Stdout.Write(out.Bytes())
}
```