Bài tập

Cho một đồ thị dạng cây gồm \(n\) đỉnh. Xét \(m\) đường đi với đỉnh xuất phát và kết thúc tương ứng là \(s_i, t_i\ (1 \le s_i \neq t_i \le n, 1 \le i \le m)\), gọi \(w_i\) là trọng số của đường đi thứ \(i\) được tính bằng tổng trọng số các cạnh trên đường đi. Nhiệm vụ của người chơi là gán trọng số các cạnh trên cây, mỗi cạnh gán giá trị bằng \(1\) hoặc \(2\) để \(w_1 \% 2 \le w_2 \% 2 \le \ldots \le w_m \% 2\).

Yêu cầu: Đếm số cách gán trọng số các cạnh thỏa mãn.

Input

• Dòng đầu chứa hai số nguyên \(n, m\ (n, m \ge 2)\).
• Dòng thứ hai gồm \(n - 1\) số mô tả cây, số thứ \(k\) là \(p_k\) cho biết đỉnh thứ \(k + 1\) nối với đỉnh \(p_k\ (1 \le p_k < k + 1)\).
• Tiếp theo là \(m\) dòng, mỗi dòng chứa hai số \(s_i, t_i\).

Output

• Gồm một dòng chứa một số nguyên \(r\) là số cách gán trọng số cho các cạnh chia dư cho \(10^9 + 7\).

Example

3 3
1 1
1 2
2 3
1 3

2

Cho \(n+1\) hình chữ nhật có cạnh song song với trục toạ độ. Hãy tìm điểm nằm trong ít nhất \(n\) hình chữ nhật. Nếu có nhiều điểm thoả mãn thì đưa ra điểm gần với điểm \((0,0)\) nhất, nếu vẫn có nhiều điểm thoả mãn thì đưa ra điểm có hoành độ nhỏ nhất.

Input

Dòng đầu chứa số \(n\)

\(n+1\) dòng tiếp theo mỗi dòng chứa \(4\) số \(x_{1},y_{1},x_{2},y_{2}\) mô tả toạ độ của hình chữ nhật.

Output

Đưa ra toạ độ điểm tìm được, hoặc đưa ra \(−1\) nếu không tồn tại.

Example

3
1 4 3 2
4 2 5 0
2 3 4 2
2 3 5 1

2 2

Scoring

\(1 \leq n \leq 2 \times 10^5\)

\(0 \leq x_{1}, y_{1}, x_{2}, y_{2} \le 10^5\).

Subtask \(1\) có \(20\) điểm : \(n, x_{1}, y_{1}, x_{2}, y_{2} \leq 200\).

Subtask \(2\) có \(30\) điểm : \(n \leq 2000\).

Subtask \(3\) có \(50\) điểm : không có ràng buộc gì thêm

Trong vương quốc Graphlandia, có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Mỗi thành phố sở hữu một chỉ số đặc biệt phản ánh nền văn minh của nó, ký hiệu là \(A[i]\). Tuy nhiên, ban đầu không có con đường nào kết nối các thành phố, khiến chúng bị cô lập.

Nhà vua của Graphlandia đã ra lệnh xây dựng hệ thống đường sá để kết nối các thành phố, nhưng ông rất quan tâm đến sự đa dạng giữa các nền văn minh. Do đó, sau mỗi lần xây dựng một con đường mới giữa hai thành phố, ông yêu cầu một báo cáo về số cặp thành phố thuộc cùng khu vực liên thông nhưng có chỉ số nền văn minh khác nhau.

Input

--- Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N \leq 3 \times 10^5, 1 \leq Q \leq 3 \times 10^5)\) --- số thành phố và số truy vấn.

--- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((1 \leq A_i \leq N)\), mỗi số mô tả chỉ số của thành phố thứ \(i\).

--- \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N, u \neq v)\), biểu thị việc xây dựng một con đường giữa \(u\) và \(v\).

Output

--- Gồm \(Q\) dòng, mỗi dòng in ra một số nguyên --- số lượng cặp thành phố có chỉ số khác nhau trong cùng khu vực liên thông sau khi truy vấn tương ứng được thực hiện.

Example

5 4
1 2 3 1 2
1 2
3 4
2 3
1 5

1
2
5
8

Để nâng cao hiệu suất vận hành cho một loại xe điện mới, các bạn trong nhóm START UP đã tiến hành thử nghiệm như sau:

Một tuyến đường được chia làm \(N\) chặng đường liên tiếp, khi xe điện chạy ở chặng thứ \(i\) của con đường, xe điện sẽ tiêu thụ một lượng \(a_i\) đơn vị năng lượng (\(a_i > 0\)) hoặc được nạp thêm một lượng \(a_i\) năng lượng nhờ hệ thống tái tạo năng lượng khi đường xuống dốc (\(a_i < 0\)). Một hành trình liên tiếp sẽ xuất phát từ chặng thứ \(i\) và kết thúc tại chặng thứ \(j\) (\(1 \leq i \leq j \leq N\)), khi đó tổng năng lượng trên hành trình đó là: \(a_i + a_{i+1} + \dots + a_j\).

Các bạn mong muốn tìm một hành trình liên tiếp dài nhất để thử nghiệm, tuy nhiên để đảm bảo an toàn cho pin và các thiết bị khác trên xe, tổng năng lượng trên một hành trình liên tiếp không được vượt quá giới hạn an toàn \(P\) của pin.

Yêu cầu: Hãy xác định số chặng đường liên tiếp dài nhất sao cho tổng các giá trị năng lượng trên đoạn đó không vượt quá giới hạn an toàn \(P\) của pin.

Input

Dữ liệu vào: Cho tệp văn bản CAU4.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên \(N\) và \(P\) (\(1 \leq N \leq 5 \times 10^5; P \leq 10^9\));
• Dòng 2: Chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \leq a_i \leq 10^9\)).

Các số trên cùng một dòng được ghi cách nhau bởi một dấu cách.

Output

Kết quả: Ghi ra tệp văn bản CAU4.OUT gồm một dòng ghi ra độ dài lớn nhất của chặng đường liên tiếp theo yêu cầu của bài toán. Biết rằng, dữ liệu đầu vào luôn đảm bảo tìm ra kết quả.

Example

5 7
8 2 2 4 1

3

Scoring

Ràng buộc:

• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 1000, -10^4 \leq a_i \leq 10^4\);
• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 10^5, 0 \leq a_i \leq 10^9\);
• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 5 \times 10^5, -10^9 \leq a_i \leq 10^9\).