Bài tập

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.

Ở 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

Trong một chuyến đi đến một thành phố xa lạ, bạn phát hiện rằng tại đây đang diễn ra \(N\) sự kiện nghệ thuật hiện đại, được đánh số từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu lúc \(S_i\) và kết thúc lúc \(E_i\).

Bạn muốn tham gia các sự kiện này bằng cách chọn một sự kiện bắt đầu \(s\) và một sự kiện kết thúc \(e\). Trong thời gian tham gia, bạn luôn ở lại đến hết sự kiện hiện tại, sau đó lập tức chuyển đến một sự kiện khác đang diễn ra (đang mở cửa).

Bạn có thể chuyển từ sự kiện \(i\) sang sự kiện \(j\) nếu và chỉ nếu \(S_j \le E_i \le E_j\).

Hãy trả lời \(Q\) truy vấn, mỗi truy vấn hỏi: số lần chuyển sự kiện ít nhất để đi từ sự kiện \(s_i\) đến sự kiện \(e_i\). Nếu không thể đi từ \(s_i\) đến \(e_i\), hãy in impossible.

\InputFile

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) --- số lượng sự kiện và số lượng truy vấn.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i, E_i\) (\(1 \le S_i < E_i \le 10^9\)) --- thời gian bắt đầu và kết thúc của sự kiện thứ \(i\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s_i, e_i\) (\(1 \le s_i, e_i \le N\)).

\OutputFile
Với mỗi truy vấn, in ra số lần chuyển sự kiện ít nhất (số nguyên), hoặc dòng impossible nếu không thể.

\Scoring

• Subtask 1 (10 điểm): Mỗi sự kiện có thể chuyển đến nhiều nhất một sự kiện khác.
• Subtask 2 (10 điểm): \(N \le 1000\), \(Q \le 100\).
• Subtask 3 (15 điểm): \(N \le 5000\).
• Subtask 4 (15 điểm): \(Q \le 100\).
• Subtask 5 (20 điểm): Không có sự kiện nào bị bao toàn bộ trong một sự kiện khác, tức là không tồn tại \(i \ne j\) sao cho \(S_i \le S_j < E_j \le E_i\).
• Subtask 6 (30 điểm): Không có ràng buộc gì thêm.

\Examples

\beginexample
\exmp
5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

2
impossible

\endexample

\Note
Ở truy vấn đầu tiên, bạn có thể đi từ sự kiện 1 \(\rightarrow\) 5 \(\rightarrow\) 4, mất 2 lần chuyển.
Ở truy vấn thứ hai, không thể từ sự kiện 3 đến sự kiện 2 vì sự kiện 2 kết thúc trước khi sự kiện 3 bắt đầu.

\endproblem

Vân có \(N\) đồ trang sức trên kệ được đánh số \(1, 2, \ldots, N\) từ trái sang phải. Đồ trang sức có nhiều loại khác nhau, được biểu thị bằng số nguyên dương. Món đồ thứ \(i\) trên kệ là loại \(A_i\).

Hôm nay Vân sẽ bay ra nước ngoài gặp gia đình và muốn mang theo càng nhiều đồ trang sức càng tốt. Tuy nhiên, vì đang vội nên Vân phải lấy một khoảng đồ trang sức liên tiếp trên kệ. Nghĩa là Vân sẽ chọn hai chỉ số, \(l\) và \(r\), và lấy tất cả các món đồ trang sức được đánh số \(l, l + 1, \ldots, r - 1, r\). Ngoài ra, do các quy tắc về thuế, an ninh sân bay sẽ vứt bỏ tất cả các loại đồ trang sức mà Vân có nhiều hơn \(S\) món trong đồ mang theo.

Ví dụ: giả sử \(S = 2\), Vân mang theo sáu món đồ trang sức: một loại \(0\), hai loại \(1\) và ba loại \(2\). Vân sẽ mất tất cả các nữ trang loại \(2\) ở sân bay!

Yêu cầu: Hãy giúp Vân chọn \(l\) và \(r\) sao cho cô ấy có thể mang được nhiều đồ trang sức nhất cho gia đình mình.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T \leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:
• Dòng một chứa hai số nguyên dương \(N\) và \(S\) (\(S \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 10^5\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là số đồ trang sức tối đa mà Vân có thể mang ra nước ngoài thăm gia đình.

Example

1
6 2
1 1 4 1 4 4

4

Scoring

\begin itemize

• Subtask \(1\) (15 điểm): \(N \le 300\).
• Subtask \(2\) (15 điểm): \(N \le 1000\).
• Subtask \(3\) (70 điểm): Không có ràng buộc nào khác.
  \end itemize