← Home
For problem statement at 0-999/600-699/640-649/645/problemD.txt this is a correct solution, but verifier at 0-999/600-699/640-649/645/verifierD.go ends with 100/100 cases passed can you fix the verifier? package main

import (
	"fmt"
	"io"
	"os"
)

func main() {
	buf, _ := io.ReadAll(os.Stdin)
	pos := 0

	nextInt := func() int {
		for pos < len(buf) && (buf[pos] < '0' || buf[pos] > '9') {
			pos++
		}
		if pos == len(buf) {
			return 0
		}
		res := 0
		for pos < len(buf) && buf[pos] >= '0' && buf[pos] <= '9' {
			res = res*10 + int(buf[pos]-'0')
			pos++
		}
		return res
	}

	n := nextInt()
	m := nextInt()
	if n == 0 {
		return
	}

	u := make([]int, m)
	v := make([]int, m)
	for i := 0; i < m; i++ {
		u[i] = nextInt()
		v[i] = nextInt()
	}

	adj := make([][]int, n+1)
	inDegree := make([]int, n+1)
	queue := make([]int, n+1)

	check := func(k int) bool {
		for i := 1; i <= n; i++ {
			adj[i] = adj[i][:0]
			inDegree[i] = 0
		}
		for i := 0; i < k; i++ {
			adj[u[i]] = append(adj[u[i]], v[i])
			inDegree[v[i]]++
		}
		head, tail := 0, 0
		for i := 1; i <= n; i++ {
			if inDegree[i] == 0 {
				queue[tail] = i
				tail++
			}
		}
		count := 0
		for head < tail {
			if tail-head > 1 {
				return false
			}
			curr := queue[head]
			head++
			count++
			for _, next := range adj[curr] {
				inDegree[next]--
				if inDegree[next] == 0 {
					queue[tail] = next
					tail++
				}
			}
		}
		return count == n
	}

	low, high := 1, m
	ans := -1

	for low <= high {
		mid := low + (high-low)/2
		if check(mid) {
			ans = mid
			high = mid - 1
		} else {
			low = mid + 1
		}
	}

	fmt.Println(ans)
}