Bài tập

Ở bài toán cuối cùng này, bạn được cho một đơn đồ thị vô hướng \(G\) gồm \(n\) đỉnh và \(m\) cạnh. Đồ thị này liên thông, nghĩa là với mọi cặp đỉnh trong đồ thị thì tồn tại ít nhất một đường đi giữa chúng.

Như ta đã biết về khái niệm cầu trong đồ thị. Cầu là một cạnh đặc biệt sao cho nếu xóa cạnh đó đi thì đồ thị mất đi tính liên thông của nó. Bài toán này không phải là đếm cầu bình thường, ta định nghĩa một cầu đặc biệt là một cạnh sao cho khi xóa hai đỉnh đầu mút của cạnh thì \(n-2\) đỉnh còn lại của \(G\) không liên thông.

Nhiệm vụ cuối cùng của bạn là đếm số lượng cầu đặc biệt có trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(4 \le n \le 100000\), \(n - 1 \le m \le 300000\)) --- số lượng hòn đảo và số lượng cây cầu.

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i, b_i \le n\)) --- biểu diễn rằng có một cây cầu nối giữa đảo \(a_i\) và đảo \(b_i\).

Đảm bảo rằng đồ thị không có không có hai cạnh kết nối cùng một cặp đỉnh.

Output

In ra một số nguyên duy nhất --- số lượng cây cầu có tính chất đặc biệt như đã mô tả.

Example

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

1

6 7
1 2
2 4
2 6
3 5
6 1
4 3
2 5

4

Scoring

• Subtask 1 (13 điểm): \(n \le 100\), \(m \le 300\)
• Subtask 2 (17 điểm): \(n \le 1000\), \(m \le 3000\)
• Subtask 3 (25 điểm): \(n \le 1000\)
• Subtask 4 (12 điểm): \(m - n \le 20\)
• Subtask 5 (33 điểm): Không có ràng buộc bổ sung

Một vùng đất hình chữ nhật có thể xem như một lưới ô vuông tạo bởi \(n\) dòng và \(m\) cột. Trên vùng đất đó, người ta đã xây dựng \(h\) đường ngang và \(v\) đường dọc. Các đường này là những đường thẳng đi qua biên của các ô trên cùng dòng hay cùng cột, bắt đầu và kết thúc trên biên của vùng đất. Các đường ngang được đánh số từ \(1\) đến \(n+1\) từ trên xuống dưới và các đường dọc được đánh số từ \(1\) đến \(m+1\) từ trái sang phải.

Để lên kế hoạch xây dựng nhà ở, người ta khảo sát vùng đất để mỗi ngôi nhà có thể xây dựng trên một mảnh đất hình vuông có diện tích \(k \times k\). Tất cả các hình vuông dựng nhà đều có diện tích bằng nhau, không phủ lên nhau, không phủ lên các con đường. Chúng có thể giáp hoặc không giáp với các con đường. Không có ô đất nào để trống. Để tiện tính toán chúng ta bỏ qua độ rộng của các con đường.

Yêu cầu: Hãy tìm những giá trị \(k\) thỏa mãn điều kiện xây dựng nhà cho dự án.

Input

Ghi ra tệp văn bản CAU2.INP:

• Dòng đầu tiên chứa ba số nguyên \(n, m, h, v\) \((1 \leq n, m \leq 10^{18}, 0 \leq h \leq 2 \times 10^5, 0 \leq v \leq 2 \times 10^5)\).

• Nếu \(h > 0\) thì dòng tiếp theo chứa \(h\) số nguyên \(h_{i}, i = 1, 2, ..., h\) \((1 \leq h_{i} \leq n + 1, 1 \leq i \leq h)\) là chỉ số các con đường ngang, tương tự nếu \(v > 0\) thì dòng tiếp theo chứa các \(v_{i}, i = 1, 2, ..., v\) \((1 \leq v_{i} \leq m + 1, 1 \leq i \leq v)\) là chỉ số của các đường dọc. Không có trường hợp \(h = 0\) và \(v > 0\) hay \(h > 0\) và \(v = 0\). Các \(h_{i}\) và \(v_{i}\) có thể trùng nhau.

• Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra tệp văn bản CAU2.OUT:

• Dòng đầu ghi một số là các giá trị \(k\) tìm được;

• Dòng thứ hai là các giá trị \(k\) tìm được, các số ghi cách nhau dấu cách và theo thứ tự tăng dần.

Example

2 4 0 0

2
1 2 

6 8 1 1
3
3

2
1 2 

44 36 3 6
25 33 9
9 37 9 21 29 9

3
1 2 4 

Scoring

• \(50\%\) số điểm có \(h = 0\) và \(v = 0\).

• \(50\%\) số điểm có \(h > 0\) và \(v > 0\). Không có hình chữ nhật nào được tạo ra bởi việc chia của của các con đường này có kích thước cạnh lớn hơn \(10^{14}\).

Vài hôm trước, A Ton đã võ mồm với bạn thân đến mức hai người ... nghỉ chơi. Vì tò mò, nhóm bạn
trong lớp muốn xem đoạn tin nhắn giữa hai người, nhưng điện thoại cậu lại đặt mật khẩu.
Mật khẩu này gồm đúng n chữ số, được lấy từ dãy số vô hạn:

\begincenter
\(12345678910111213141516171819...\)
\endcenter

Trong đó, chữ số thứ \(i\) trong mật khẩu chính là chữ số ở vị trí \(a_i\) trong dãy số trên.
Hãy giúp nhóm bạn xuất ra dãy mật khẩu của A Ton.

Input

Dữ liệu vào HACMAY.INP:

• Dòng đầu: số nguyên \(n\) \((1 \leq n \leq 10^5)\).
• Dòng thứ hai: \(n\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^{18})\).

Output

Dữ liệu ra HACMAY.OUT:

• In ra \(n\) chữ số tương ứng với các vị trí trong dãy vô hạn.

Example

6
1 23 31 10 33 11

160110

Scoring

Ràng buộc:

• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^3\).
• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^6\).
• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^{12}\).
• \(40\%\) test còn lại: Không có ràng buộc thêm.

Cho hai dãy số nguyên dương độ dài \(n\): \(a = (a_1, a_2, \dots, a_n)\) và \(b = (b_1, b_2, \dots, b_n)\). Biết rằng các phần tử của hai dãy đều là các số nguyên dương thuộc tập \(\{1, 2, \dots, n\}\).

Ta định nghĩa một phép biến đổi như sau: chọn hai chỉ số \(i\) và \(j\) thỏa \(1 \le i \le j \le n\), rồi hoán đổi hai đoạn con \(a_i, a_{i+1}, \dots, a_j\) và \(b_i, b_{i+1}, \dots, b_j\) giữa hai dãy. Sau phép hoán đổi thu được hai dãy mới:

Nếu sau khi thực hiện phép biến đổi như trên có ít nhất một trong hai dãy \(a'\) hoặc \(b'\) là một hoán vị của tập \(\{1, 2, \dots, n\}\) thì ta nói phép biến đổi đó tạo ra một hoán vị trộn.

Yêu cầu: Với mỗi test, hãy xác định có bao nhiêu cặp \((i, j)\) khác nhau sẽ tạo ra hoán vị trộn theo định nghĩa trên.

Input

• Dòng \(1\): chứa số nguyên \(t\) (\(t \le 5\)) — số test.
• Mỗi test gồm ba dòng:
• Dòng đầu của test chứa số nguyên \(n\) (\(1 \le n \le 2 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (mọi \(a_i \le n\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\) (mọi \(b_i \le n\)).

Output

Ghi ra \(t\) dòng, mỗi dòng là một số nguyên — số cách (số cặp \((i, j)\) khác nhau) có thể tạo ra hoán vị trộn cho test tương ứng.

Scoring

• Subtask 1 (30%): \(n \le 100\).
• Subtask 2 (30%): \(n \le 5000\).
• Subtask 3 (40%): không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

8
3