Cho cây có ~n~ đỉnh, đỉnh thứ ~i~ ghi số ~a_i~. Đỉnh ~1~ là gốc cây.

Xét một dãy các đỉnh ~v_1, v_2, \dots, v_k~ sao cho ~v_i~ là tổ tiên (không nhất thiết là cha) của ~v_{i+1}~. Dãy các đỉnh này được coi là đẹp nếu ~a_{v_1} \le a_{v_2} \le \dots \le a_{v_k}~. Hay nói cách khác, các số ghi trên các đỉnh này tạo thành một dãy không giảm.

Hỏi dãy đẹp dài nhất của cây này (tính theo số đỉnh) là bao nhiêu và có bao nhiêu dãy đẹp có độ dài như vậy.

DỮ LIỆU VÀO

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^6)~.
• Dòng thứ ba chứa ~n-1~ số nguyên ~p_2, p_3, \dots, p_n~ ~(1 \le p_i \le n)~. Trong đó ~p_i~ là cha của đỉnh ~i~.

Dữ liệu bảo đảm đồ thị có dạng cây.

DỮ LIỆU RA

Ghi ra hai số nguyên cách nhau bởi dấu cách:

• Số thứ nhất là độ dài lớn nhất.
• Số thứ hai là số dãy đẹp có độ dài đó, theo modulo 11092019.

DỮ LIỆU VÀO MẪU

4 
1 5 3 6
1 2 3

DỮ LIỆU RA MẪU

3 2

Giải thích:

• Hai dãy đỉnh thoả mãn là: ~(1, 2, 4)~ và ~(1, 3, 4)~.

Hãy tìm ma trận ~A~ gồm các số ~0, 1~ thoả mãn tất cả các điều kiện sau:

• Tổng các số trên dòng thứ ~i~ là ~r_i~.
• Tổng các số trên cột thứ ~i~ là ~c_i~.
• ~A~ có thứ tự từ điển bé nhất có thể.

Ma trận ~A~ được gọi là có thứ tự từ điển nhỏ hơn ma trận ~B~ (hai ma trận cùng có ~m~ hàng và ~n~ cột) nếu lần lượt so sánh từng phần tử theo từng hàng từ trên xuống dưới, trên mỗi hàng theo thứ tự từ trái sang phải để tìm phần tử khác nhau đầu tiên thì tại vị trí đó giá trị phần tử của ma trận ~A~ nhỏ hơn giá trị phần tử của ma trận ~B~.

DỮ LIỆU VÀO

• Dòng đầu chứa hai số nguyên ~m, n~ ~(1 \le m, n \le 80)~.
• Dòng thứ hai chứa ~m~ số nguyên ~r_1, r_2, \dots, r_m~.
• Dòng thứ ba chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~.

DỮ LIỆU RA

In ra ma trận ~A~. Nếu không có đáp án, in ra ~-1~.

DỮ LIỆU VÀO MẪU

3 3 
2 1 2 
1 2 2

DỮ LIỆU RA MẪU

011 
001 
110

(Bài được lấy cảm hứng từ đề IMO siêu dễ của 10 năm trước. Không làm được thì lên diutúp xem chữa đề IMO bảo đảm nghĩ ra bài này luôn: link 100% không phải rick roll)

Cho ~n~ điểm trên mặt phẳng sao cho không có ba điểm nào thẳng hàng. Ta thực hiện quá trình sau:

1. Chọn một điểm ~A~ trong ~n~ điểm đó làm điểm xoay.
2. Vẽ một đường thẳng ~d~ đi qua điểm ~A~ đã chọn nhưng không đi qua điểm nào trong ~n-1~ điểm còn lại.
3. Quay đường thẳng ~d~ quanh điểm xoay theo chiều kim đồng hồ cho tới khi chạm vào một điểm ~P~ khác điểm xoay.
4. Đặt điểm ~P~ mới chạm vào này làm điểm xoay mới. Tăng số đếm của ~P~ ~(cnt_P)~ lên ~1~ đơn vị.
5. Quay lại bước 3.

Quá trình cứ tiếp diễn tương tự cho tới khi đường thẳng ~d~ quay được đủ một vòng ~360~ độ so với vị trí ban đầu ở bước 2. (Nếu ai chưa hiểu đề thì xem vid ở trên tự động hiểu).

Hãy tìm cách chọn điểm ~A~ và đường thẳng ~d~ ban đầu để sao cho khi kết thúc quá trình, ~max(cnt_1, cnt_2, \dots, cnt_n)~ đạt giá trị lớn nhất có thể. Hay nói cách khác, hãy tìm cấu hình ban đầu để trong quá trình, có 1 điểm được chọn làm điểm xoay nhiều lần nhất có thể.

DỮ LIỆU VÀO

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~(x_i, y_i)~ là toạ độ của điểm thứ ~i~ ~(-10^5 \le x_i, y_i \le 10^5)~.

Dữ liệu bảo đảm các điểm là phân biệt và không có ba điểm thẳng hàng.

DỮ LIỆU RA

In ra một số duy nhất là ~max(cnt_1, cnt_2, \dots, cnt_n)~ lớn nhất có thể.

DỮ LIỆU VÀO MẪU

3
-1 0
1 0
0 2

DỮ LIỆU RA MẪU

2

Giải thích: