← Home
For problem statement at 1000-1999/1300-1399/1360-1369/1361/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1360-1369/1361/verifierE.go ends with case 33 failed
expected:
1 2 3

got:
1

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"io"
	"math/rand"
	"os"
	"time"
)

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 {
		c := fs.data[fs.idx]
		if c >= '0' && c <= '9' {
			break
		}
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return val
}

func writeInt(w *bufio.Writer, x int) {
	if x == 0 {
		w.WriteByte('0')
		return
	}
	if x < 0 {
		w.WriteByte('-')
		x = -x
	}
	var buf [20]byte
	i := len(buf)
	for x > 0 {
		i--
		buf[i] = byte('0' + x%10)
		x /= 10
	}
	w.Write(buf[i:])
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	rng := rand.New(rand.NewSource(time.Now().UnixNano()))
	t := in.NextInt()

	for ; t > 0; t-- {
		n := in.NextInt()
		m := in.NextInt()

		adj := make([][]int, n+1)
		for i := 0; i < m; i++ {
			u := in.NextInt()
			v := in.NextInt()
			adj[u] = append(adj[u], v)
		}

		parent := make([]int, n+1)
		tin := make([]int, n+1)
		tout := make([]int, n+1)
		it := make([]int, n+1)
		orderArr := make([]int, n)
		stackArr := make([]int, n)

		runCheck := func(root int, collect bool) (bool, []int, []int, []int, []int) {
			for i := 1; i <= n; i++ {
				parent[i] = 0
				tin[i] = 0
				tout[i] = 0
				it[i] = 0
			}

			orderLen := 0
			stackLen := 1
			stackArr[0] = root
			timer := 0

			for stackLen > 0 {
				u := stackArr[stackLen-1]
				if tin[u] == 0 {
					timer++
					tin[u] = timer
				}
				if it[u] < len(adj[u]) {
					v := adj[u][it[u]]
					it[u]++
					if tin[v] == 0 {
						parent[v] = u
						stackArr[stackLen] = v
						stackLen++
					}
				} else {
					timer++
					tout[u] = timer
					orderArr[orderLen] = u
					orderLen++
					stackLen--
				}
			}

			if orderLen != n {
				return false, nil, nil, nil, nil
			}

			var backT, backH []int
			if collect {
				backT = make([]int, 0, m)
				backH = make([]int, 0, m)
			}

			for u := 1; u <= n; u++ {
				for _, v := range adj[u] {
					if parent[v] == u {
						continue
					}
					if !(tin[v] <= tin[u] && tout[u] <= tout[v]) {
						return false, nil, nil, nil, nil
					}
					if collect {
						backT = append(backT, u)
						backH = append(backH, v)
					}
				}
			}

			return true, parent, orderArr[:orderLen], backT, backH
		}

		const sampleLimit = 120
		root := 0

		if n <= sampleLimit {
			for v := 1; v <= n; v++ {
				ok, _, _, _, _ := runCheck(v, false)
				if ok {
					root = v
					break
				}
			}
		} else {
			perm := make([]int, n)
			for i := 0; i < n; i++ {
				perm[i] = i + 1
			}
			for i := 0; i < sampleLimit; i++ {
				j := i + rng.Intn(n-i)
				perm[i], perm[j] = perm[j], perm[i]
			}
			for i := 0; i < sampleLimit; i++ {
				v := perm[i]
				ok, _, _, _, _ := runCheck(v, false)
				if ok {
					root = v
					break
				}
			}
		}

		if root == 0 {
			writeInt(out, -1)
			out.WriteByte('\n')
			continue
		}

		ok, parentRes, order, backT, backH := runCheck(root, true)
		if !ok {
			writeInt(out, -1)
			out.WriteByte('\n')
			continue
		}

		cnt := make([]int, n+1)
		xv := make([]int, n+1)
		headOf := make([]int, len(backH)+1)

		for i := 0; i < len(backH); i++ {
			id := i + 1
			u := backT[i]
			a := backH[i]
			cnt[u]++
			cnt[a]--
			xv[u] ^= id
			xv[a] ^= id
			headOf[id] = a
		}

		for _, u := range order {
			p := parentRes[u]
			if p != 0 {
				cnt[p] += cnt[u]
				xv[p] ^= xv[u]
			}
		}

		good := make([]bool, n+1)
		for i := len(order) - 1; i >= 0; i-- {
			u := order[i]
			if u == root {
				good[u] = true
			} else if cnt[u] == 1 {
				good[u] = good[headOf[xv[u]]]
			}
		}

		k := 0
		for i := 1; i <= n; i++ {
			if good[i] {
				k++
			}
		}

		if k*5 < n {
			writeInt(out, -1)
			out.WriteByte('\n')
			continue
		}

		first := true
		for i := 1; i <= n; i++ {
			if good[i] {
				if !first {
					out.WriteByte(' ')
				}
				first = false
				writeInt(out, i)
			}
		}
		out.WriteByte('\n')
	}
}