package main
import (
"bytes"
"io"
"os"
"sort"
"strconv"
)
const LOG = 20
const INF = int(1e9)
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) NextInt() int {
for fs.idx < fs.n {
c := fs.data[fs.idx]
if c >= '0' && c <= '9' {
break
}
fs.idx++
}
val := 0
for fs.idx < fs.n {
c := fs.data[fs.idx]
if c < '0' || c > '9' {
break
}
val = val*10 + int(c-'0')
fs.idx++
}
return val
}
type Dual struct {
size int
data []int
}
func NewDual(n int) *Dual {
size := 1
for size < n {
size <<= 1
}
data := make([]int, size<<1)
for i := range data {
data[i] = INF
}
return &Dual{size: size, data: data}
}
func (d *Dual) RangeChMin(l, r, val int) {
l += d.size - 1
r += d.size - 1
for l <= r {
if l&1 == 1 {
if val < d.data[l] {
d.data[l] = val
}
l++
}
if r&1 == 0 {
if val < d.data[r] {
d.data[r] = val
}
r--
}
l >>= 1
r >>= 1
}
}
func (d *Dual) Point(p int) int {
idx := p + d.size - 1
res := INF
for idx > 0 {
if d.data[idx] < res {
res = d.data[idx]
}
idx >>= 1
}
return res
}
type Point struct {
x int
y int
}
type Rect struct {
l1 int
r1 int
l2 int
r2 int
idx int
}
type Event struct {
y int
l int
r int
idx int
sign int
}
type Pair struct {
v int
h int
}
var (
n int
parentUp [][]int
parent []int
depth []int
heavy []int
headH []int
pos []int
tout []int
subSize []int
busUp [][]int
childHead []int
childTo []int
childNext []int
)
func ancestorAtDepth(x, targetDepth int) int {
diff := depth[x] - targetDepth
k := 0
for diff > 0 {
if diff&1 == 1 {
x = parentUp[k][x]
}
diff >>= 1
k++
}
return x
}
func lca(a, b int) int {
if depth[a] < depth[b] {
a, b = b, a
}
diff := depth[a] - depth[b]
k := 0
for diff > 0 {
if diff&1 == 1 {
a = parentUp[k][a]
}
diff >>= 1
k++
}
if a == b {
return a
}
for k = LOG - 1; k >= 0; k-- {
if parentUp[k][a] != parentUp[k][b] {
a = parentUp[k][a]
b = parentUp[k][b]
}
}
return parentUp[0][a]
}
func updatePath(a, b, val int, dual *Dual) {
for headH[a] != headH[b] {
if depth[headH[a]] < depth[headH[b]] {
a, b = b, a
}
dual.RangeChMin(pos[headH[a]], pos[a], val)
a = parent[headH[a]]
}
if depth[a] > depth[b] {
a, b = b, a
}
dual.RangeChMin(pos[a], pos[b], val)
}
func distToAncestor(x, anc int) (int, int, bool) {
if x == anc {
return 0, anc, true
}
cur := x
steps := 0
for k := LOG - 1; k >= 0; k-- {
nxt := busUp[k][cur]
if nxt != 0 && depth[nxt] > depth[anc] {
cur = nxt
steps += 1 << k
}
}
nxt := busUp[0][cur]
if nxt != 0 && depth[nxt] <= depth[anc] {
return steps + 1, cur, true
}
return 0, 0, false
}
func bitAdd(bit []int, idx, val int) {
for idx <= n {
bit[idx] += val
idx += idx & -idx
}
}
func bitSum(bit []int, idx int) int {
res := 0
for idx > 0 {
res += bit[idx]
idx -= idx & -idx
}
return res
}
func main() {
fs := NewFastScanner()
n = fs.NextInt()
parent = make([]int, n+1)
depth = make([]int, n+1)
childHead = make([]int, n+1)
for i := 1; i <= n; i++ {
childHead[i] = -1
}
childTo = make([]int, n)
childNext = make([]int, n)
ec := 0
for i := 2; i <= n; i++ {
p := fs.NextInt()
parent[i] = p
depth[i] = depth[p] + 1
childTo[ec] = i
childNext[ec] = childHead[p]
childHead[p] = ec
ec++
}
parentUp = make([][]int, LOG)
parentUp[0] = parent
for k := 1; k < LOG; k++ {
parentUp[k] = make([]int, n+1)
prev := parentUp[k-1]
cur := parentUp[k]
for v := 1; v <= n; v++ {
cur[v] = prev[prev[v]]
}
}
subSize = make([]int, n+1)
heavy = make([]int, n+1)
best := make([]int, n+1)
for i := 1; i <= n; i++ {
subSize[i] = 1
}
for v := n; v >= 2; v-- {
p := parent[v]
subSize[p] += subSize[v]
if subSize[v] > best[p] {
best[p] = subSize[v]
heavy[p] = v
}
}
headH = make([]int, n+1)
pos = make([]int, n+1)
tout = make([]int, n+1)
stack := make([]Pair, 0, n)
stack = append(stack, Pair{1, 1})
curPos := 1
for len(stack) > 0 {
pr := stack[len(stack)-1]
stack = stack[:len(stack)-1]
v, h := pr.v, pr.h
for x := v; x != 0; x = heavy[x] {
headH[x] = h
pos[x] = curPos
curPos++
for e := childHead[x]; e != -1; e = childNext[e] {
c := childTo[e]
if c != heavy[x] {
stack = append(stack, Pair{c, c})
}
}
}
}
for v := 1; v <= n; v++ {
tout[v] = pos[v] + subSize[v] - 1
}
dual := NewDual(n)
m := fs.NextInt()
pointsByL := make([][]Point, n+1)
for i := 0; i < m; i++ {
a := fs.NextInt()
b := fs.NextInt()
l := lca(a, b)
updatePath(a, b, depth[l], dual)
if l != a && l != b {
x, y := pos[a], pos[b]
if x > y {
x, y = y, x
}
pointsByL[l] = append(pointsByL[l], Point{x, y})
}
}
up1 := make([]int, n+1)
for v := 1; v <= n; v++ {
md := dual.Point(pos[v])
if md < depth[v] {
up1[v] = ancestorAtDepth(v, md)
}
}
busUp = make([][]int, LOG)
busUp[0] = up1
for k := 1; k < LOG; k++ {
busUp[k] = make([]int, n+1)
prev := busUp[k-1]
cur := busUp[k]
for v := 1; v <= n; v++ {
cur[v] = prev[prev[v]]
}
}
q := fs.NextInt()
ans := make([]int, q)
rectByL := make([][]Rect, n+1)
for i := 0; i < q; i++ {
v := fs.NextInt()
u := fs.NextInt()
l := lca(v, u)
if l == v {
d, _, ok := distToAncestor(u, l)
if ok {
ans[i] = d
} else {
ans[i] = -1
}
continue
}
if l == u {
d, _, ok := distToAncestor(v, l)
if ok {
ans[i] = d
} else {
ans[i] = -1
}
continue
}
dv, pv, ok1 := distToAncestor(v, l)
du, pu, ok2 := distToAncestor(u, l)
if !ok1 || !ok2 {
ans[i] = -1
continue
}
ans[i] = dv + du
l1, r1 := pos[pv], tout[pv]
l2, r2 := pos[pu], tout[pu]
if l1 > l2 {
l1, l2 = l2, l1
r1, r2 = r2, r1
}
rectByL[l] = append(rectByL[l], Rect{l1, r1, l2, r2, i})
}
bit := make([]int, n+2)
for l := 1; l <= n; l++ {
rects := rectByL[l]
if len(rects) == 0 {
continue
}
pts := pointsByL[l]
if len(pts) == 0 {
continue
}
sort.Slice(pts, func(i, j int) bool {
return pts[i].y < pts[j].y
})
events := make([]Event, 0, len(rects)*2)
for i, r := range rects {
events = append(events, Event{r.r2, r.l1, r.r1, i, 1})
events = append(events, Event{r.l2 - 1, r.l1, r.r1, i, -1})
}
sort.Slice(events, func(i, j int) bool {
return events[i].y < events[j].y
})
cnt := make([]int, len(rects))
pi := 0
for _, e := range events {
for pi < len(pts) && pts[pi].y <= e.y {
bitAdd(bit, pts[pi].x, 1)
pi++
}
cnt[e.idx] += e.sign * (bitSum(bit, e.r) - bitSum(bit, e.l-1))
}
for i, r := range rects {
if cnt[i] > 0 {
ans[r.idx]--
}
}
for i := 0; i < pi; i++ {
bitAdd(bit, pts[i].x, -1)
}
}
var out bytes.Buffer
for i := 0; i < q; i++ {
out.WriteString(strconv.Itoa(ans[i]))
out.WriteByte('\n')
}
_, _ = os.Stdout.Write(out.Bytes())
}