Quan hệ giữa các nhân viên trong một công ty được tổ chức theo cấu trúc phân cấp. Công ty có tổng cộng $n$ nhân viên. Mỗi nhân viên được gán một số hiệu duy nhất từ $1$ đến $n$, và giám đốc có số hiệu $1$. Mỗi nhân viên, trừ giám đốc, có đúng một cấp trên trực tiếp. Cấp trên trực tiếp của nhân viên $i$ có số hiệu $p_i$, với $p_i<i$.

Nhân viên $x$ là cấp dưới mức $1$ của nhân viên $y$ nếu $p_x=y$. Với $k>1$, nhân viên $x$ là cấp dưới mức $k$ của nhân viên $y$ nếu nhân viên $p_x$ là cấp dưới mức $k-1$ của nhân viên $y$.

Giám đốc có cơ hội cử một số nhân viên tham gia khóa học nâng cao trình độ. Ông quyết định chọn hai số $L$ và $R$, rồi cử tất cả nhân viên có số hiệu $i$ thỏa mãn $L \le i \le R$ đi học.

Trước khi chọn $L$ và $R$, giám đốc nhận được $m$ nguyện vọng từ nhân viên. Nguyện vọng thứ $j$ được mô tả bằng hai số $u_j$ và $k_j$, có nghĩa là nhân viên $u_j$ muốn một trong các cấp dưới mức $k_j$ của mình được cử đi học. Để tiết kiệm chi phí, giám đốc muốn chọn $L$ và $R$ sao cho số nhân viên được cử đi học nhỏ nhất có thể, đồng thời đáp ứng tất cả nguyện vọng.

Hãy viết chương trình, dựa trên quan hệ cấp trên–cấp dưới và các nguyện vọng, tìm hai số $L$ và $R$ sao cho việc cử tất cả nhân viên có số hiệu từ $L$ đến $R$, kể cả hai đầu, đi học sẽ đáp ứng mọi nguyện vọng và số nhân viên được cử đi học là nhỏ nhất có thể. Nếu có nhiều cặp $L,R$ tối ưu, hãy tìm cặp có $L$ nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của tệp vào chứa số $n$, là số nhân viên của công ty ($2 \le n \le 200\,000$). Dòng thứ hai chứa $n-1$ số $p_2,p_3,\ldots,p_n$ ($1 \le p_i<i$), là số hiệu của các cấp trên trực tiếp.

Dòng thứ ba chứa số $m$, là số nguyện vọng của nhân viên.

$m$ dòng tiếp theo mô tả các nguyện vọng, mỗi dòng chứa hai số nguyên $u_j,k_j$ ($1 \le u_j<n$, $1 \le k_j<n$; bảo đảm nhân viên $u_j$ có ít nhất một cấp dưới mức $k_j$).

Dữ liệu ra

In ra hai số cần tìm $L$ và $R$. Nếu có nhiều cặp $(L,R)$ tối ưu, hãy in cặp có $L$ nhỏ nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3 6

Ghi chú

Các nhân viên có số hiệu $3$, $4$, $5$ và $6$ sẽ được cử đi học. Nhân viên $3$ là cấp dưới mức $1$ của nhân viên $1$; nhân viên $4$ là cấp dưới mức $2$ của nhân viên $1$; nhân viên $6$ là cấp dưới mức $1$ của nhân viên $3$.

Nhiệm vụ con

Điểm của mỗi nhiệm vụ con chỉ được trao nếu vượt qua tất cả các kiểm thử của nhiệm vụ con đó và các nhiệm vụ con cần thiết.

Thông tin về kết quả chấm cuối cùng

Khi được yêu cầu, điểm của từng nhiệm vụ con sẽ được thông báo.