Bài tập

Có \(n\) thành phố và ban đầu không có con đường nào giữa chúng. Tuy nhiên, mỗi ngày một con đường mới sẽ được xây dựng, và sẽ có tổng cộng \(m\) con đường.

Một thành phần là một nhóm các thành phố mà trong đó có một tuyến đường giữa hai thành phố bất kỳ sử dụng các con đường đã được xây dựng. Sau mỗi ngày, nhiệm vụ của bạn là tìm ra số lượng thành phần và kích thước của thành phần lớn nhất.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và đường. Các thành phố được đánh số \(1,2,\ldots,n\).

• Sau đó, có \(m\) dòng mô tả các con đường mới. Mỗi dòng có hai số nguyên \(a\) và \(b\): một con đường mới được xây dựng giữa các thành phố \(a\) và \(b\).

• Bạn có thể giả định rằng tất cả con đường sẽ được xây dựng giữa hai thành phố khác nhau.

Output

• In \(m\) dòng: thông tin yêu cầu sau mỗi ngày.

Example

5 3
1 2
1 3
4 5

4 2
3 3
2 3

Cho một dãy \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Yêu cầu: Đếm tất cả các cặp chỉ số \(i, j\) \((1 \le i \le j \le n)\) sao cho tổng các phần tử liên tiếp từ chỉ số \(i\) đến chỉ số \(j\) trong dãy \(A\) là một số chẵn.

Cụ thể, ta định nghĩa:
$
S_{ij} = a_i + a_{i+1} + \dots + a_j
$

Yêu cầu: Đếm số lượng cặp \((i, j)\) sao cho \(S_{ij}\) là số chẵn.

Input

Dữ liệu được đọc từ file CPAIR.INP:

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)) --- số phần tử của dãy \(A\).
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a_i\) (\(1 \le a_i \le 10^9\)) --- phần tử thứ \(i\) của dãy.

Output

Ghi ra file CPAIR.OUT một dòng duy nhất chứa số nguyên --- kết quả bài toán: số lượng cặp \((i, j)\) thoả mãn điều kiện tổng là số chẵn.

Example

4
2
5
6
8

4

Scoring

• 20% test có \(1 \le n \le 10^2\), \(1 \le a_i \le 10^9\)
• 20% test có \(1 \le n \le 10^3\), \(1 \le a_i \le 10^9\)
• 60% test có \(1 \le n \le 10^6\), \(1 \le a_i \le 10^9\)

"Tùng tùng tùng...".

Trong buổi học cuối cùng của một năm học đầy kỷ niệm, cô giáo chủ nhiệm muốn tạo ra một món quà nhỏ để ghi nhớ lớp học thân thương. Cô nảy ra một ý tưởng: phát một tờ giấy trắng để tất cả học sinh trong lớp cùng ký tên, tạo thành một kỷ vật đáng nhớ.

Cô xếp \(N\) học sinh ngồi theo hình vòng tròn, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Sau đó, cô phát một tờ giấy cho một học sinh bất kỳ và yêu cầu bạn ấy ký tên lên đó. Tờ giấy sau đó được truyền đi giữa các học sinh theo quy tắc sau:

• Tờ giấy có thể được chuyền cho học sinh bên trái hoặc bên phải của học sinh đang nắm giữ tờ giấy.
• Ngoài ra, mỗi học sinh còn có thể chọn chuyền tờ giấy cho một học sinh khác là một trong những người bạn thân của họ. Cô giáo được biết trong lớp có \(N-3\) cặp bạn thân và cô đã cố tính sắp xếp, sao cho không có một cặp bạn thân ngồi liền kề, và nếu ta vẽ các đường nối giữa họ trên mặt phẳng, thì không có hai đường nào cắt nhau (ngoại trừ tại các đầu mút). Xem hình minh họa.

Mỗi học sinh chỉ ký tên đúng một lần. Quy trình sẽ kết thúc khi học sinh đầu tiên ký nhận lại tờ giấy, và tạo thành một vòng tuần hoàn khép kín gồm các chữ ký. Lưu ý, ta không tính các tập hợp chữ ký có lực lượng nhỏ hơn 3.

Hai tập hợp chữ ký được xem là khác nhau nếu tồn tại một chữ ký chỉ thuộc một trong hai tập hợp.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) --- số học sinh trong lớp.
• Mỗi dòng trong số \(N - 3\) dòng tiếp theo chứa hai số nguyên \(X_i, Y_i\) \((1 \leq X_i, Y_i \leq N)\) --- là một cặp bạn thân.

Output

In ra một số nguyên --- số tập hợp chữ ký khác nhau mà cô giáo có thể nhận được, lấy phần dư theo \(10^9 + 7\).

Example

5
1 3
3 5

6

6
2 4
4 6
6 2

11

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 13 & \(N \leq 15\)

2 & 18 & \(N \leq 300\)

3 & 34 & \(N \leq 2000\)

4 & 15 & Luôn có cặp bạn thân giữa học sinh \(1\) và \(k\) với mọi \(k = 3, 4, \dots, N - 1\)

5 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^6, 1 \leq i \leq n \leq 10^6\)).

**Yêu cầu:** Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con không giảm, nếu có nhiều dãy con thoả mãn thì in ra các dãy con theo thứ tự xuất hiện.

Input

Vào từ file SUBSEQ.INP gồm:

• Dòng đầu: số nguyên dương \(n\);
• Dòng tiếp theo: \(n\) số nguyên dương cách nhau khoảng trắng.

Output

Ghi ra file SUBSEQ.OUT gồm:

• Dòng đầu: tổng lớn nhất tìm được;
• Các dòng tiếp theo: các dãy con thỏa mãn.

Example

10
2 2 3 4 6 6 7 7 8 8

53
2 2 3 4 6 6 7 7 8 8 

11
4 7 4 5 7 4 9 3 3 4 6

16
4 5 7 
3 3 4 6 

Scoring

Ràng buộc:

• Có 20% số điểm ứng với \(n = 10\) và dãy không giảm;
• Có 20% số điểm ứng với \((11 \leq n \leq 200)\);
• Có 20% số điểm ứng với \((201 \leq n \leq 10^3)\);
• 40% số điểm còn lại ứng với \((10^3 < n \leq 10^6)\).