← Home
For problem statement at 1000-1999/1300-1399/1360-1369/1368/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1360-1369/1368/verifierE.go ends with wrong answer on test 2
input:
 1
5 5
3 5
2 5
1 5
3 4
4 5

expected:
 1
5

got:
 2
4 5


exit status 1 can you fix the verifier? ```go
package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	// Configure scanner for fast I/O
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < t; i++ {
		solve(scanner, writer)
	}
}

func solve(sc *bufio.Scanner, wr *bufio.Writer) {
	if !sc.Scan() {
		return
	}
	n, _ := strconv.Atoi(sc.Text())
	if !sc.Scan() {
		return
	}
	m, _ := strconv.Atoi(sc.Text())

	adj := make([][]int, n+1)
	for i := 0; i < m; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		v, _ := strconv.Atoi(sc.Text())
		adj[u] = append(adj[u], v)
	}

	// Compute L[u]: length of the longest path ending at u
	// Since x < y for all edges x->y, we can iterate 1 to n
	L := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if L[i] == 0 {
			L[i] = 1
		}
		for _, v := range adj[i] {
			if L[i]+1 > L[v] {
				L[v] = L[i] + 1
			}
		}
	}

	// Precompute bitmasks of neighbors' L[u]%7
	mod := make([]int, n+1)
	inM := make([]int, n+1)
	outM := make([]int, n+1)

	for i := 1; i <= n; i++ {
		mod[i] = L[i] % 7
	}

	for u := 1; u <= n; u++ {
		ub := 1 << mod[u]
		for _, v := range adj[u] {
			outM[u] |= (1 << mod[v])
			inM[v] |= ub
		}
	}

	// We need to keep at least 3/7 of nodes
	target := (3*n + 6) / 7
	bestMask := 0

	// Try all possible masks of length modulo 7
	// There are 2^7 = 128 masks
	for mk := 0; mk < 128; mk++ {
		cnt := 0
		for u := 1; u <= n; u++ {
			if (mk>>mod[u])&1 == 1 {
				// We keep u if it's in the mask, unless it's a "transit" node
				// A transit node is one that has both potential incoming and outgoing edges 
				// from/to nodes allowed by the mask.
				if (inM[u]&mk) != 0 && (outM[u]&mk) != 0 {
					continue
				}
				cnt++
			}
		}
		if cnt >= target {
			bestMask = mk
			break
		}
	}

	// Identify removed spots based on the best mask
	removed := make([]int, 0, n)
	for u := 1; u <= n; u++ {
		keep := false
		if (bestMask>>mod[u])&1 == 1 {
			// Same check as above
			if !((inM[u]&bestMask) != 0 && (outM[u]&bestMask) != 0) {
				keep = true
			}
		}
		if !keep {
			removed = append(removed, u)
		}
	}

	// Output result
	wr.WriteString(strconv.Itoa(len(removed)))
	wr.WriteByte('\n')
	for i, v := range removed {
		if i > 0 {
			wr.WriteByte(' ')
		}
		wr.WriteString(strconv.Itoa(v))
	}
	wr.WriteByte('\n')
}
```