← Home
For problem statement at 1000-1999/1100-1199/1100-1109/1103/problemC.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1100-1109/1103/verifierC.go ends with build oracle failed: exit status 1
# command-line-arguments
./1103C.go:5:2: "fmt" imported and not used

exit status 1 can you fix the verifier? package main

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

type FastScanner struct {
	data []byte
	idx  int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data}
}

func (fs *FastScanner) NextInt() int {
	n := len(fs.data)
	for fs.idx < n {
		c := fs.data[fs.idx]
		if (c >= '0' && c <= '9') || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.idx < n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * 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 outputOne(w *bufio.Writer, v, a int, parent, depth []int) {
	size := depth[v] - depth[a] + 1
	writeInt(w, size)
	w.WriteByte('\n')
	writeInt(w, v)
	w.WriteByte(' ')
	writeInt(w, a)
	tmp := make([]int, 0, size-2)
	cur := parent[v]
	for cur != a {
		tmp = append(tmp, cur)
		cur = parent[cur]
	}
	for i := len(tmp) - 1; i >= 0; i-- {
		w.WriteByte(' ')
		writeInt(w, tmp[i])
	}
	w.WriteByte('\n')
}

func outputTwo(w *bufio.Writer, v, a, b int, parent, depth []int) {
	size := depth[b] - depth[a] + 2
	writeInt(w, size)
	w.WriteByte('\n')
	writeInt(w, v)
	w.WriteByte(' ')
	writeInt(w, a)
	tmp := make([]int, 0, size-2)
	cur := b
	for cur != a {
		tmp = append(tmp, cur)
		cur = parent[cur]
	}
	for i := len(tmp) - 1; i >= 0; i-- {
		w.WriteByte(' ')
		writeInt(w, tmp[i])
	}
	w.WriteByte('\n')
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	m := fs.NextInt()
	k := fs.NextInt()

	head := make([]int, n+1)
	for i := 1; i <= n; i++ {
		head[i] = -1
	}
	to := make([]int, 2*m)
	next := make([]int, 2*m)
	edgeCnt := 0

	for i := 0; i < m; i++ {
		u := fs.NextInt()
		v := fs.NextInt()

		to[edgeCnt] = v
		next[edgeCnt] = head[u]
		head[u] = edgeCnt
		edgeCnt++

		to[edgeCnt] = u
		next[edgeCnt] = head[v]
		head[v] = edgeCnt
		edgeCnt++
	}

	parent := make([]int, n+1)
	depth := make([]int, n+1)
	child := make([]int, n+1)
	it := make([]int, n+1)
	visited := make([]bool, n+1)

	for i := 1; i <= n; i++ {
		it[i] = head[i]
	}

	stack := make([]int, 0, n)
	stack = append(stack, 1)
	visited[1] = true
	depth[1] = 1
	deepest := 1

	for len(stack) > 0 {
		v := stack[len(stack)-1]
		e := it[v]
		if e == -1 {
			stack = stack[:len(stack)-1]
			continue
		}
		it[v] = next[e]
		u := to[e]
		if u == parent[v] {
			continue
		}
		if !visited[u] {
			visited[u] = true
			parent[u] = v
			depth[u] = depth[v] + 1
			if depth[u] > depth[deepest] {
				deepest = u
			}
			child[v]++
			stack = append(stack, u)
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer w.Flush()

	target := (n + k - 1) / k
	if depth[deepest] >= target {
		w.WriteString("PATH\n")
		path := make([]int, 0, depth[deepest])
		for v := deepest; v != 0; v = parent[v] {
			path = append(path, v)
		}
		writeInt(w, len(path))
		w.WriteByte('\n')
		for i := len(path) - 1; i >= 0; i-- {
			if i != len(path)-1 {
				w.WriteByte(' ')
			}
			writeInt(w, path[i])
		}
		w.WriteByte('\n')
		return
	}

	leaves := make([]int, 0, k)
	for i := 1; i <= n && len(leaves) < k; i++ {
		if child[i] == 0 {
			leaves = append(leaves, i)
		}
	}

	if len(leaves) < k {
		w.WriteString("-1\n")
		return
	}

	w.WriteString("CYCLES\n")
	for _, v := range leaves {
		x, y := 0, 0
		for e := head[v]; e != -1; e = next[e] {
			u := to[e]
			if u == parent[v] {
				continue
			}
			if x == 0 {
				x = u
			} else if y == 0 && u != x {
				y = u
				break
			}
		}

		if x == 0 || y == 0 {
			w.WriteString("-1\n")
			return
		}

		if depth[x] > depth[y] {
			x, y = y, x
		}

		len1 := depth[v] - depth[x] + 1
		len2 := depth[v] - depth[y] + 1

		if len1%3 != 0 {
			outputOne(w, v, x, parent, depth)
		} else if len2%3 != 0 {
			outputOne(w, v, y, parent, depth)
		} else {
			outputTwo(w, v, x, y, parent, depth)
		}
	}
}