For problem statement at 1000-1999/1900-1999/1930-1939/1932/problemG.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1930-1939/1932/verifierG.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type Item struct {
	v int
	d int64
}

type PQ []*Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].d < pq[j].d }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(*Item))
}
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func extGCD(a, b int64) (g, x, y int64) {
	if b == 0 {
		return a, 1, 0
	}
	g, x1, y1 := extGCD(b, a%b)
	return g, y1, x1 - (a/b)*y1
}

func solve(A, C, H int64) int64 {
	g, x, _ := extGCD(A, H)
	if C%g != 0 {
		return -1
	}
	H /= g
	C /= g
	x %= H
	if x < 0 {
		x += H
	}
	k := (x * (C % H)) % H
	if k < 0 {
		k += H
	}
	return k
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 1024*1024)
	scanner.Split(bufio.ScanWords)

	readInt := func() int {
		scanner.Scan()
		res := 0
		sign := 1
		for _, c := range scanner.Bytes() {
			if c == '-' {
				sign = -1
			} else {
				res = res*10 + int(c-'0')
			}
		}
		return res * sign
	}

	readInt64 := func() int64 {
		scanner.Scan()
		var res int64 = 0
		var sign int64 = 1
		for _, c := range scanner.Bytes() {
			if c == '-' {
				sign = -1
			} else {
				res = res*10 + int64(c-'0')
			}
		}
		return res * sign
	}

	if !scanner.Scan() {
		return
	}
	t_cases := 0
	for _, c := range scanner.Bytes() {
		t_cases = t_cases*10 + int(c-'0')
	}

	for t := 0; t < t_cases; t++ {
		n := readInt()
		m := readInt()
		H := readInt64()

		L := make([]int64, n+1)
		for i := 1; i <= n; i++ {
			L[i] = readInt64()
		}

		S := make([]int64, n+1)
		for i := 1; i <= n; i++ {
			S[i] = readInt64()
		}

		adj := make([][]int, n+1)
		for i := 0; i < m; i++ {
			u := readInt()
			v := readInt()
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		dist := make([]int64, n+1)
		for i := 1; i <= n; i++ {
			dist[i] = -1
		}

		pq := &PQ{}
		heap.Init(pq)

		dist[1] = 0
		heap.Push(pq, &Item{v: 1, d: 0})

		ans := int64(-1)

		for pq.Len() > 0 {
			curr := heap.Pop(pq).(*Item)
			u := curr.v
			d := curr.d

			if d > dist[u] {
				continue
			}

			if u == n {
				ans = d
				break
			}

			for _, v := range adj[u] {
				A := (S[u] - S[v]) % H
				if A < 0 {
					A += H
				}
				B := (L[v] - L[u]) % H
				if B < 0 {
					B += H
				}
				C := (B - (A*(d%H))%H) % H
				if C < 0 {
					C += H
				}

				k := solve(A, C, H)
				if k != -1 {
					new_d := d + k + 1
					if dist[v] == -1 || new_d < dist[v] {
						dist[v] = new_d
						heap.Push(pq, &Item{v: v, d: new_d})
					}
				}
			}
		}

		fmt.Println(ans)
	}
}