Bài tập

Bạn được cho 2 số nguyên \(a, b\).

Hãy làm việc này sau đây cho đến khi một trong hai số \(a, b\) là số 0 :

• Nếu \(b \leq a\) thì lấy a trừ đi b \((a = a - b)\).
• ngươc lại lấy b trừ a\((b = b - a)\).

Nhập vào 2 số \(a, b\). Hãy đếm số lần bạn làm công việc trên

Input

• \(t (t \leq 1000)\) - số test

• \(t\) dòng, mỗi dòng gồm 2 số nguyên dương \(a, b (a, b \leq 1000000000)\)

Output

• \(t\) dòng, số lần thực hiện để một trong 2 số \(a, b\) có 1 số là số 0

Example

1
4 17

8

Cho một đồ thị vô hướng liên thông có trọng số gồm \(n\) đỉnh, \(m\) cạnh. Cạnh thứ \(i\ (1 \le i \le m)\) nối hai đỉnh \(u_i\) và \(v_i\ (1 \le u_i \neq v_i \le n)\) với trọng số là \(2^i\).

Yêu cầu: Cho \(k\) đỉnh đặc biệt \(s_1, s_2, \ldots, s_k\), hãy chọn ra các cạnh với tổng trọng số nhỏ nhất
để liên thông được \(k\) đỉnh.

Input

• Dòng đầu chứa ba số \(n, m, k\ (n, m, k \le 3.10^5)\).
• Dòng thứ \(i\) trong \(m\) dòng, mỗi dòng chứa hai số \(u_i, v_i\).
• Dòng cuối cùng chứa \(k\) số nguyên mô tả \(k\) đỉnh đặc biệt.

Output

• Gồm một dòng chứa \(m\) số, số thứ \(i\) bằng số \(1\) hoặc \(0\) tương ứng là cạnh thứ \(i\) được chọn hoặc không được chọn.

Example

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

0 1 1 0 

Tương truyền, San Hà Xã Tắc Đồ là một pháp bảo vô cùng cường đại do Nữ Oa nương nương thời thượng
cổ lưu lại. Uy lực của bức họa này có thể tạo dựng cả một thế giới riêng -- thiên địa sinh thành, nhật nguyệt vận hành, vạn vật hữu linh đều có thể hiện ra trong tranh. Ai nắm giữ được bức họa, chẳng khác nào nắm giữ một cõi thế giới riêng biệt trong lòng bàn tay.

Lâm là một đạo sĩ đã tu luyện đến cảnh giới gần kề thánh nhân, trong một lần cơ duyên gặp gỡ, tìm được một bức họa cổ, tương truyền là bản phác San Hà Xã Tắc Đồ.

Sau nhiều năm tu hành và nghiên ngẫm, ông Lâm quyết định dựng lại bức họa, từng đoạn từng nét. Bức tranh cần được vẽ lên một tấm lụa dài \(n\) thước, chia làm \(n\) đoạn liên tiếp, mỗi đoạn ứng với một phần của thế giới trong tranh. Ông đã xác định được mức màu sắc thích hợp cho từng đoạn, được lưu dưới dạng dãy chuỗi dài \(n\) số, mỗi số cho biết độ sáng, tối tương ứng được sử dụng.

Ban đầu, toàn bộ tấm lụa trắng trơn. Mỗi lần hành pháp (tức là vẽ), ông có thể tô một đoạn liên tiếp trên lụa bằng một màu duy nhất, nhưng ông không được tô màu sáng hơn lên màu tối hơn, vì điều đó sẽ khiến thiên địa trong tranh lộn ngược, âm dương đảo lộn. Chỉ có thể tô màu tối hơn chỗ chưa vẽ, hoặc lên màu sáng hơn.

Tuy nhiên, do thiên mệnh hữu hạn, Lâm không thể hoàn thành toàn bộ bức họa trong một lần. Vì thế, ông đang cân nhắc bỏ trống một số đoạn nhất định, không vẽ vào đó nữa -- để sau này hậu nhân hoàn thiện. Hiện tại có \(q\) kịch bản khác nhau, mỗi kịch bản cho biết một đoạn liên tiếp từ \(l\) đến \(r\) trên tấm lụa sẽ được vẽ.

Yêu cầu: Với mỗi kịch bản như vậy, hãy giúp ông Lâm tính xem: số lần hành pháp (vẽ) ít nhất cần thiết để hoàn thành bức họa, đúng theo màu sắc đã định, và không vi phạm quy tắc sáng tối.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\) (\(n, q \leq 10^5\)) là số đoạn của tấm lụa và số kịch bản.
• Dòng thứ hai là \(n\) số \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)) biểu thị độ sáng tối của từng đoạn.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq n\)) cho biết đoạn sẽ vẽ.

Output

• Với mỗi kịch bản, in ra một dòng chứa số nguyên là số lần vẽ tối thiểu cần thiết để hoàn thành bức họa.

Example

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

2
4
4
3
5

Scoring

• \(30\%\) số điểm thỏa mãn \(n, q \leq 100\)
• \(20\%\) số điểm khác với \(n, q \leq 1000\)
• Còn lại không có điều kiện gì thêm

Đất nước ABC có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và các con đường nối giữa các thành phố là đường đi hai chiều. Hệ thống giao thông đó đảm bảo luôn đi được từ một thành phố bất kỳ đến một thành phố khác thông qua các đường đi.

Nam đang dự định đi du lịch đất nước ABC, chuyến đi của cậu bắt đầu từ thành phố \(s\) và kết thúc tại thành phố \(t\). Nam có thể di chuyển tự do giữa các thành phố và cậu có thể thăm lại thành phố mà cậu đã thăm với số lần tùy thích, nhưng nếu đến thành phố \(t\) thì Nam sẽ kết thúc hành trình của mình. Nam sẽ chụp một bức ảnh ở thành phố đầu tiên của chuyến đi nếu \(s \le t\). Sau đó, mỗi khi cậu đến một thành phố có chỉ số lớn hơn tất cả thành phố đã được thăm, cậu sẽ chụp thêm một bức ảnh ở thành phố đó. Đồng thời, Nam cũng muốn chụp một bức ảnh ở thành phố kết thúc nếu nó thỏa mãn điều kiện chụp ảnh trên.

Yêu cầu: Nam có \(q\) lựa chọn, mỗi lựa chọn cho biết thành phố xuất phát \(s\) và thành phố kết thúc \(t\). Bạn hãy cho biết số lượng ảnh tối đa cậu ấy có thể chụp trong suốt chuyến đi từ \(s\) đến \(t\), hoặc không có hành trình nào với điều kiện như vậy.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(1 \le n \le 5000\), \(n-1 \le m \le \min(\frac{n(n-1)}{2}, 5000)\)) lần lượt là số thành phố ở đất nước ABC và số con đường nối các thành phố.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) (\(1 \le u, v \le n\)) thể hiện một đường đi hai chiều nối hai thành phố \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 2 \times 10^5\)) là số lựa chọn của Nam.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(s, t\) (\(1 \le s, t \le n\)) thể hiện một lựa chọn của Nam.

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

Output

• Gồm \(q\) dòng, theo thứ tự lựa chọn của Nam trong tệp dữ liệu vào, mỗi dòng ghi một số là số lượng bức ảnh lớn nhất mà Nam chụp được trong hành trình lựa chọn đó. Nếu không có hành trình như vậy thì ghi ra \(-1\).

Example

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

2
2
-1
1

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

4
-1

3 2
1 3
3 2
2
1 1
1 2

1
-1

Scoring

• 20% số tests tương ứng với 20% số điểm của bài có: \(q \le 1000, s+1 = t\) với mọi lựa chọn.
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000, q \le 1000\).
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000\).
• 40% số tests còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.