← Home
For problem statement at 0-999/800-899/850-859/859/problemE.txt this is a correct solution, but verifier at 0-999/800-899/850-859/859/verifierE.go ends with All tests passed can you fix the verifier? package main

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

const MOD int64 = 1000000007

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] == ' ' || data[idx] == '\n' || data[idx] == '\r' || data[idx] == '\t') {
			idx++
		}
		sign := 1
		if idx < len(data) && data[idx] == '-' {
			sign = -1
			idx++
		}
		val := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return sign * val
	}

	n := nextInt()
	c := make([]int, n)
	d := make([]int, n)
	owner := make([]int, 2*n+1)

	for i := 0; i < n; i++ {
		c[i] = nextInt()
		d[i] = nextInt()
		owner[c[i]] = i + 1
	}

	targetType := make([]int, n)
	target := make([]int, n)

	for i := 0; i < n; i++ {
		if d[i] == c[i] {
			targetType[i] = 2
			target[i] = i
		} else if owner[d[i]] == 0 {
			targetType[i] = 1
			target[i] = d[i]
		} else {
			targetType[i] = 0
			target[i] = owner[d[i]] - 1
		}
	}

	state := make([]int, n)
	rootKind := make([]int, n)
	rootID := make([]int, n)
	sinkSize := make([]int, 2*n+1)
	cycleCount := 0
	path := make([]int, 0, n)

	for i := 0; i < n; i++ {
		if state[i] != 0 {
			continue
		}
		path = path[:0]
		cur := i
		kind := 0
		id := 0

		for {
			if state[cur] == 0 {
				state[cur] = 1
				path = append(path, cur)
				if targetType[cur] == 1 {
					kind = 1
					id = target[cur]
					break
				}
				if targetType[cur] == 2 {
					kind = 2
					id = target[cur]
					break
				}
				cur = target[cur]
				continue
			}
			if state[cur] == 1 {
				cycleCount++
				kind = 3
				id = cycleCount
				break
			}
			kind = rootKind[cur]
			id = rootID[cur]
			break
		}

		for _, u := range path {
			state[u] = 2
			rootKind[u] = kind
			rootID[u] = id
		}
		if kind == 1 {
			sinkSize[id] += len(path)
		}
	}

	ans := int64(1)
	for i := 1; i <= 2*n; i++ {
		if sinkSize[i] > 0 {
			ans = ans * int64(sinkSize[i]+1) % MOD
		}
	}
	for i := 0; i < cycleCount; i++ {
		ans = ans * 2 % MOD
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprint(out, ans)
	out.Flush()
}