For problem statement at 1000-1999/1700-1799/1700-1709/1702/problemG1.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1700-1709/1702/verifierG1.go ends with output line count mismatch
exit status 1 can you fix the verifier? package main
import (
"bytes"
"io"
"os"
)
const LOG = 20
var up [][]int
var depth []int
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) NextInt() int {
for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
fs.idx++
}
val := 0
for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
val = val*10 + int(fs.data[fs.idx]-'0')
fs.idx++
}
return val
}
func lca(a, b int) int {
if depth[a] < depth[b] {
a, b = b, a
}
diff := depth[a] - depth[b]
i := 0
for diff > 0 {
if diff&1 == 1 {
a = up[i][a]
}
diff >>= 1
i++
}
if a == b {
return a
}
for i = LOG - 1; i >= 0; i-- {
if up[i][a] != up[i][b] {
a = up[i][a]
b = up[i][b]
}
}
return up[0][a]
}
func dist(a, b int) int {
c := lca(a, b)
return depth[a] + depth[b] - 2*depth[c]
}
func main() {
fs := NewFastScanner()
n := fs.NextInt()
adj := make([][]int, n+1)
for i := 0; i < n-1; i++ {
u := fs.NextInt()
v := fs.NextInt()
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
up = make([][]int, LOG)
for i := 0; i < LOG; i++ {
up[i] = make([]int, n+1)
}
depth = make([]int, n+1)
queue := make([]int, 0, n)
queue = append(queue, 1)
for head := 0; head < len(queue); head++ {
v := queue[head]
for _, to := range adj[v] {
if to == up[0][v] {
continue
}
up[0][to] = v
depth[to] = depth[v] + 1
queue = append(queue, to)
}
}
for j := 1; j < LOG; j++ {
prev := up[j-1]
cur := up[j]
for v := 1; v <= n; v++ {
cur[v] = prev[prev[v]]
}
}
q := fs.NextInt()
var out bytes.Buffer
for ; q > 0; q-- {
k := fs.NextInt()
p := make([]int, k)
for i := 0; i < k; i++ {
p[i] = fs.NextInt()
}
if k <= 2 {
out.WriteString("YES\n")
continue
}
s := p[0]
a := s
best := -1
for _, x := range p {
d := dist(s, x)
if d > best {
best = d
a = x
}
}
b := a
best = -1
for _, x := range p {
d := dist(a, x)
if d > best {
best = d
b = x
}
}
dab := best
ok := true
for _, x := range p {
if dist(a, x)+dist(x, b) != dab {
ok = false
break
}
}
if ok {
out.WriteString("YES\n")
} else {
out.WriteString("NO\n")
}
}
os.Stdout.Write(out.Bytes())
}