← Home
For problem statement at 0-999/700-799/790-799/794/problemD.txt this is a correct solution, but verifier at 0-999/700-799/790-799/794/verifierD.go ends with all tests passed can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
	"sort"
	"strconv"
)

func appendU32(b []byte, x uint32) []byte {
	return append(b, byte(x), byte(x>>8), byte(x>>16), byte(x>>24))
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	nextInt := func() int {
		for p < len(data) && (data[p] < '0' || data[p] > '9') {
			p++
		}
		v := 0
		for p < len(data) && data[p] >= '0' && data[p] <= '9' {
			v = v*10 + int(data[p]-'0')
			p++
		}
		return v
	}

	n := nextInt()
	m := nextInt()

	adj := make([][]int, n)
	eu := make([]int, m)
	ev := make([]int, m)

	for i := 0; i < m; i++ {
		u := nextInt() - 1
		v := nextInt() - 1
		eu[i] = u
		ev[i] = v
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	for i := 0; i < n; i++ {
		sort.Ints(adj[i])
	}

	classMap := make(map[string]int, n)
	classOf := make([]int, n)
	k := 0

	for i := 0; i < n; i++ {
		neigh := adj[i]
		buf := make([]byte, 0, 4*(len(neigh)+1))
		inserted := false
		for _, to := range neigh {
			if !inserted && i < to {
				buf = appendU32(buf, uint32(i))
				inserted = true
			}
			buf = appendU32(buf, uint32(to))
		}
		if !inserted {
			buf = appendU32(buf, uint32(i))
		}
		s := string(buf)
		id, ok := classMap[s]
		if !ok {
			id = k
			classMap[s] = id
			k++
		}
		classOf[i] = id
	}

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

	if k == 1 {
		out := make([]byte, 0, 4+2*n)
		out = append(out, 'Y', 'E', 'S', '\n')
		for i := 0; i < n; i++ {
			if i > 0 {
				out = append(out, ' ')
			}
			out = append(out, '1')
		}
		out = append(out, '\n')
		w.Write(out)
		return
	}

	qAdj := make([][]int, k)
	seen := make(map[uint64]struct{}, m)

	for i := 0; i < m; i++ {
		a := classOf[eu[i]]
		b := classOf[ev[i]]
		if a == b {
			continue
		}
		if a > b {
			a, b = b, a
		}
		key := uint64(uint32(a))<<32 | uint64(uint32(b))
		if _, ok := seen[key]; !ok {
			seen[key] = struct{}{}
			qAdj[a] = append(qAdj[a], b)
			qAdj[b] = append(qAdj[b], a)
		}
	}

	endpoints := make([]int, 0, 2)
	ok := true
	for i := 0; i < k; i++ {
		d := len(qAdj[i])
		if d == 1 {
			endpoints = append(endpoints, i)
		} else if d != 2 {
			ok = false
			break
		}
	}

	if !ok || len(endpoints) != 2 {
		w.WriteString("NO\n")
		return
	}

	labelOfClass := make([]int, k)
	prev := -1
	cur := endpoints[0]
	label := 1
	visited := 0

	for {
		if labelOfClass[cur] != 0 {
			ok = false
			break
		}
		labelOfClass[cur] = label
		visited++

		next := -1
		for _, to := range qAdj[cur] {
			if to != prev {
				next = to
				break
			}
		}
		if next == -1 {
			break
		}
		prev, cur = cur, next
		label++
	}

	if !ok || visited != k {
		w.WriteString("NO\n")
		return
	}

	out := make([]byte, 0, 4+12*n)
	out = append(out, 'Y', 'E', 'S', '\n')
	for i := 0; i < n; i++ {
		if i > 0 {
			out = append(out, ' ')
		}
		out = strconv.AppendInt(out, int64(labelOfClass[classOf[i]]), 10)
	}
	out = append(out, '\n')
	w.Write(out)
}