← Home
For problem statement at 0-999/600-699/620-629/623/problemA.txt this is a correct solution, but verifier at 0-999/600-699/620-629/623/verifierA.go ends with All tests passed can you fix the verifier? package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	if _, err := fmt.Fscan(in, &n, &m); err != nil {
		return
	}

	adj := make([][]bool, n)
	for i := 0; i < n; i++ {
		adj[i] = make([]bool, n)
	}

	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		u--
		v--
		adj[u][v] = true
		adj[v][u] = true
	}

	neigh := make([][]int, n)
	degH := make([]int, n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i != j && !adj[i][j] {
				neigh[i] = append(neigh[i], j)
			}
		}
		degH[i] = len(neigh[i])
	}

	color := make([]int, n)
	for i := 0; i < n; i++ {
		color[i] = -1
	}

	for i := 0; i < n; i++ {
		if degH[i] > 0 && color[i] == -1 {
			q := make([]int, 0, n)
			q = append(q, i)
			color[i] = 0
			for head := 0; head < len(q); head++ {
				u := q[head]
				for _, v := range neigh[u] {
					if color[v] == -1 {
						color[v] = 1 - color[u]
						q = append(q, v)
					} else if color[v] == color[u] {
						fmt.Fprintln(out, "No")
						return
					}
				}
			}
		}
	}

	label := make([]byte, n)
	for i := 0; i < n; i++ {
		if degH[i] == 0 {
			label[i] = 'b'
		} else {
			if color[i] == 0 {
				label[i] = 'a'
			} else {
				label[i] = 'c'
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			acPair := (label[i] == 'a' && label[j] == 'c') || (label[i] == 'c' && label[j] == 'a')
			if acPair {
				if adj[i][j] {
					fmt.Fprintln(out, "No")
					return
				}
			} else {
				if !adj[i][j] {
					fmt.Fprintln(out, "No")
					return
				}
			}
		}
	}

	fmt.Fprintln(out, "Yes")
	fmt.Fprintln(out, string(label))
}