TKPC - Bảo Anh vs Đức Thuận

Đất nước Byteland có \(N\) thành phố (được đánh số từ \(1\) đến \(N\)) và \(M\) con đường hai chiều kết nối chúng với nhau. Con đường thứ \(i\) kết nối thành phố \(u_i\) với thành phố \(v_i\) và có độ dài \(c_i\). Oanh Trúc Béo muốn đi thăm thú một số cặp thành phố bằng chiếc xe Yamaha Grande của cô ấy. Bình xăng của chiếc xe này có thể chứa tối đa \(L\) lít xăng, và ở mỗi đơn vị độ dài thì chiếc xe sẽ tiêu thụ đúng \(1\) lít xăng. Cô ấy chỉ có thể đổ đầy lại bình xăng khi đang ở một trong \(N\) thành phố của Byteland (cũng đồng nghĩa với việc chiếc xe Grande này không thể hết xăng khi đang đi giữa một con đường nào đó).

Bạn hãy lập trình xử lý \(Q\) truy vấn. Mỗi truy vấn cho trước hai số nguyên \(s_i\), \(t_i\) và yêu cầu bạn tính số lần ít nhất Oanh Trúc Béo cần đổ đầy lại bình xăng nếu muốn di chuyển từ thành phố \(s_i\) đến thành phố \(t_i\) (bình xăng của cô ấy đã đầy sẵn lúc xuất phát tại \(s_i\) nên bạn không cần tính vào). Nếu không tồn tại một lộ trình di chuyển hợp lệ thì in ra \(-1\).

Input

• Dòng đầu chứa ba số nguyên \(N\), \(M\) và \(L\) (\(2\leq N\leq 300\), \(0\leq M\leq \dfrac{N(N-1)}{2}\), \(1\leq L\leq 10^9\)).

• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\) và \(c_i\) (\(u_i\neq v_i\), \(1\leq c_i\leq 10^9\)). Dữ liệu đảm bảo mỗi cặp thành phố được nối với nhau bởi tối đa một con đường.

• Dòng tiếp theo chứa số nguyên dương \(Q\) (\(1\leq Q\leq N(N-1)\)).

• Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\) (\(s_i \neq t_i\)).

Output

• In ra \(Q\) dòng là câu trả lời tương ứng cho từng truy vấn.

Example

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

0
1

4 0 1
1
2 1

-1

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

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0

Bảo Huy là chú ếch đẹp trai nhất đầm sen ITK19. Đầm sen này được chia thành một bảng ô vuông gồm \(M\) hàng (đánh số từ trên xuống dưới) và \(N\) cột (đánh số từ trái qua phải). Ta quy ước ô nằm ở giao điểm của hàng \(i\) và cột \(j\) là ô \((i, j)\). Một số ô trong đầm có chứa một lá sen nổi (ký hiệu o) để Huy có thể nhảy lên, các ô còn lại có 100% bề mặt là nước (ký hiệu là .). Huy cần nhảy từ ô có ký tự S đến ô có ký tự T (hai ô này đều mặc định chứa một lá sen) theo quy tắc: ở mỗi bước anh chỉ có thể nhảy từ ô hiện tại đến một ô chứa lá sen trên cùng hàng hoặc cùng cột. CaiWinDao muốn bỏ đi một số lá sen trong đầm (trừ hai lá tại S và T) để Huy không còn có thể nhảy từ S đến T nữa. Các bạn hãy lập trình giúp CaiWinDao xác định số lá sen ít nhất cần bỏ đi nhé!

Input

• Dòng đầu hai số nguyên dương \(M\) và \(N\) \((2\leq M, N\leq 100)\).

• \(M\) dòng sau, mỗi dòng chứa \(N\) ký tự mô tả đầm sen.

Output

• Một số nguyên là số lượng lá sen ít nhất cần bỏ để Huy không thể nhảy từ S đến T. Nếu không tìm được phương án thỏa mãn thì in ra \(-1\).

Example

3 3
S.o
.o.
o.T

2

3 4
S...
.oo.
...T

0

4 3
.S.
.o.
.o.
.T.

-1

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo

5

Tùng Dương có một cây (đồ thị vô hướng liên thông và không có chu trình) gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Dương đặt tên cây này là \(\textbf{cây Nhi}\). Mỗi cạnh của cây Nhi đều được tô một màu nào đó trong \(N-1\) màu có sẵn (các màu này được đánh mã từ \(1\) đến \(N-1\)). Cạnh thứ \(i\) của cây Nhi nối đỉnh \(u_i\) với đỉnh \(v_i\), đồng thời có độ dài \(d_i\) và được tô màu với mã màu là \(c_i\). Dương nhờ bạn lập trình trả lời \(Q\) truy vấn, trong đó, truy vấn thứ \(j\) cho biết bốn số nguyên \(x_j\), \(y_j\), \(u_j\), \(v_j\) và yêu cầu bạn cập nhật độ dài của tất cả các cạnh được tô màu với mã màu \(x_j\) thành \(y_j\), sau đó in ra khoảng cách giữa đỉnh \(u_j\) và đỉnh \(v_j\) (các thay đổi trên không được áp dụng cho các truy vấn tiếp theo).

Bạn hãy ra tay giúp đỡ Dương làm chủ được cây Nhi nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(2\leq N\leq 10^5\), \(1\leq Q\leq 10^5\)).

• Dòng thứ \(i\) trong \(N-1\) dòng tiếp theo chứa bốn số nguyên \(u_i\), \(v_i\), \(c_i\) và \(d_i\).

• Dòng thứ \(j\) trong \(Q\) dòng tiếp theo chứa bốn số nguyên \(x_j\), \(y_j\), \(u_j\) và \(v_j\).

Output

• In ra \(Q\) dòng là câu trả lời cho các truy vấn tương ứng.

Example

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

130
200
60

Lớp ITK19 vừa chia rẽ sâu sắc sau một drama. Giờ đây, cả lớp đã chia thành hai phe: phe áo đen và phe áo trắng, mỗi phe có đúng \(n\) học sinh. Để giải quyết mâu thuẫn, mỗi người ở phe này sẽ bóc phốt đúng một người ở phe bên kia. Ta quy ước một hạt nhân là một tập con \(S\) gồm các học sinh trong lớp ITK19 thỏa mãn hai tính chất sau:

• Không có học sinh nào thuộc \(S\) bị bóc phốt bởi một học sinh khác cũng thuộc \(S\).
• Mỗi học sinh không thuộc \(S\) đều bị bóc phốt bởi một học sinh thuộc \(S\).

Hãy lập trình tìm một hạt nhân của lớp ITK19. Dữ liệu đảm bảo tồn tại ít nhất một hạt nhân.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((1\leq n\leq 10^5)\) là số lượng học sinh của mỗi phe. Các học sinh của phe áo đen được đánh số từ \(1\) đến \(n\), còn những học sinh của phe áo trắng sẽ được đánh số từ \(n+1\) đến \(2n\).

• Dòng tiếp theo chứa \(n\) số nguyên dương \(f_1\), \(f_2\),..., \(f_n\) - trong đó \(f_k\) là số hiệu của học sinh bị bóc phốt bởi học sinh \(k\) \((n+1\leq f_k\leq 2n)\).

• Dòng cuối cùng chứa \(n\) số nguyên dương \(s_1\), \(s_2\),..., \(s_n\) - trong đó \(s_k\) là số hiệu của học sinh bị bóc phốt bởi học sinh \(n+k\) \((1\leq s_k\leq n)\).

Output

• In ra số hiệu của các học sinh trong hạt nhân mà bạn tìm được. Nếu có nhiều phương án thì bạn chỉ cần in ra một phương án bất kỳ.

Example

4
5 6 7 7
1 3 2 3

1 2 4 8

Phòng học của lớp ITK19 vừa đổi từ khóa cơ sang khóa điện tử. Mật khẩu của khóa điện tử này là một đoạn mã nhị phân độ dài \(3n\), các bit của đoạn mã này được đánh số từ \(1\) đến \(3n\) theo chiều từ trái sang phải. Ta quy ước trọng số của một mã nhị phân bằng với \(1\) cộng cho số cặp bit kề nhau mà khác nhau. Ví dụ, đoạn mã 000 có trọng số là 1 còn đoạn mã 011010100 có trọng số là \(7\).

Bảo Khoa muốn trọng số của mã khóa phải lớn hơn hoặc bằng \(2n\) nên anh ấy đang nghiên cứu tìm ra một dãy thao tác để biến đổi mã khóa ban đầu. Ở mỗi thao tác, Bảo Khoa có thể chọn hai bit kề nhau trong đoạn mã và đảo chúng. Bạn hãy lập trình xác định một dãy thao tác có độ dài không quá \(n\) để biến đổi mã khóa ban đầu thành một mã khóa mới có trọng số ít nhất là \(2n\). Dữ liệu đảm bảo luôn tồn tại một cách biến đổi thỏa mãn.

Input

• Gồm một dòng duy nhất chứa một đoạn mã khóa có \(3n\) bit với \(1 \leq n \leq 10^5\).

Ouput

• Dòng đầu tiên ghi ra số nguyên \(m (0 \leq m \leq n)\) là số thao tác cần thực hiện.

• Dòng tiếp theo ghi ra \(m\) số chỉ số nguyên \(a_1, a_2,\cdots, a_m\) thể hiện phương án đảo bit bạn tìm được. Số nguyên \(a_k\) thể hiện chỉ số của bit bên trái trong hai bit được đảo ở thao tác thứ \(k\).

• Nếu đoạn mã ban đầu đã có trọng số lớn hơn hoặc bằng \(2n\) sẵn, bạn chỉ cần in ra số \(0\).

Example

000000000 

3
2 5 6

111001000111

2
3 9

010101 

0

Trong buổi sinh hoạt đầu năm, cô giáo chủ nhiệm giao cho Công Đức chụp lại một số tấm ảnh kỷ niệm cho lớp ITK19. Công Đức yêu cầu tất cả \(N\) bạn học sinh trong lớp (không tính cậu ấy) xếp thành một hàng và đánh số các bạn từ \(1\) đến \(N\) từ đầu hàng đến cuối hàng. Sau đó, cậu ấy chụp tổng cộng \(M\) tấm ảnh, tấm ảnh thứ \(i\) ghi lại hình ảnh một đoạn con từ học sinh \(a_i\) đến học sinh \(b_i\).

Sau khi quan sát \(M\) tấm ảnh được chụp, cô giáo nhận ra một hiện tượng: trong mỗi tấm ảnh có đúng một học sinh không mặc đồng phục! Vì số ảnh quá lớn nên cô rất ngại rà soát ngược lại từng tấm để điểm tên những học sinh này. Cô liền nhờ Đức lập trình xác định số lượng tối đa các bạn học sinh trong lớp không mặc đồng phục (không tính Đức) theo ràng buộc trên. Các bạn hãy giúp Đức nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M (1 \le/q N \leq 2 \times 10^5, 1 \leq M \leq 10^5)\).

• Dòng thứ \(i\) trong \(M\) dòng sau chứa hai số nguyên dương \(a_i\) và \(b_i\).

Ouput

• Một số nguyên là số lượng lớn nhất có thể các học sinh không mặc đồng phục. Nếu không tìm được nghiệm thoả mãn thì in ra \(−1\).

Example

5 3
1 4
2 5
3 4 

1