Samarbetet mellan de anställda i ett företag är organiserat i en hierarkisk struktur. Företaget har totalt $n$ anställda. Varje anställd har ett unikt nummer från $1$ till $n$, och direktören har nummer $1$. Varje anställd utom direktören har exakt en omedelbar chef. Den omedelbara chefen för anställd $i$ har nummer $p_i$, där $p_i<i$.

Anställd $x$ är underställd anställd $y$ på nivå $1$ om $p_x=y$. För $k>1$ är anställd $x$ underställd anställd $y$ på nivå $k$ om anställd $p_x$ är underställd anställd $y$ på nivå $k-1$.

Företagets direktör har fått möjlighet att skicka vissa anställda på fortbildningskurser. Han bestämmer sig därför för att välja två tal $L$ och $R$ och skicka alla anställda med nummer $i$ sådana att $L\le i\le R$ på kurserna.

Innan direktören väljer $L$ och $R$ får han $m$ önskemål från företagets anställda. Det $j$:e önskemålet anges med två tal $u_j$ och $k_j$ och innebär att anställd $u_j$ ber att en av hans underställda på nivå $k_j$ ska skickas på kurs. För att spara pengar vill direktören välja $L$ och $R$ så att antalet anställda som skickas på fortbildning är så litet som möjligt, samtidigt som alla önskemål uppfylls.

Skriv ett program som, utifrån företagets chefsrelationer och de anställdas önskemål, bestämmer två tal $L$ och $R$ så att alla önskemål uppfylls om alla anställda med nummer från $L$ till $R$, inklusive ändpunkterna, skickas på fortbildningskurser, och så att antalet anställda som skickas är så litet som möjligt. Om det finns flera optimala par $L,R$, ska det par där $L$ är minst hittas.

Indata

Den första raden i indatafilen innehåller talet $n$ — antalet anställda i företaget ($2\le n\le 200\,000$). Den andra raden innehåller $n-1$ tal: $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$) — numren på de anställdas omedelbara chefer.

Den tredje raden innehåller talet $m$ — antalet önskemål från de anställda.

De följande $m$ raderna anger de anställdas önskemål och innehåller två heltal vardera, $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$; det garanteras att anställd $u_j$ har minst en underställd på nivå $k_j$).

Utdata

Skriv ut de två sökta talen $L$ och $R$. Om det finns flera optimala par $(L,R)$, ska det par där $L$ är minst skrivas ut.

Exempel

Indata 1

7
1 1 2 2 3 3
3
1 1
3 1
1 2

Utdata 1

3 6

Förklaring

De anställda med nummer $3$, $4$, $5$ och $6$ skickas på fortbildning. Anställd $3$ är underställd anställd $1$ på nivå $1$, anställd $4$ är underställd anställd $1$ på nivå $2$, och anställd $6$ är underställd anställd $3$ på nivå $1$.

Deluppgifter

Poäng för en deluppgift ges endast om alla tester i den deluppgiften och de nödvändiga deluppgifterna klaras.

Information om resultaten av den slutliga bedömningen

På begäran meddelas poängen för varje deluppgift.