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())
}
```