Cây, Cây khung, Cây khung nhỏ nhất

Có \(N\) thùng nước được đánh số từ 1 đến \(N\), giữa 2 thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thái ban đầu tất cả các van đều đóng.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có 2 dạng:

• Dạng X Y 1 có ý nghĩa là bạn cần mở van nối giữa 2 thùng \(X\) và \(Y\).
• Dạng X Y 2 có ý nghĩa là bạn cần cho biết với trạng thái các van đang mở / khóa như hiện tại thì 2 thùng \(X\) và \(Y\) có thuộc cùng một nhóm bình thông nhau hay không? Hai thùng được coi là thuộc cùng một nhóm bình thông nhau nếu nước từ bình này có thể chảy đến được bình kia qua một số ống có van đang mở.

Input

• Dòng đầu tiên ghi một số nguyên dương \(P\) là số yêu cầu.
• Trong \(P\) dòng tiếp theo, mỗi dòng ghi ba số nguyên dương \(X, Y, Z\) với ý nghĩa có yêu cầu loại \(Z\) với 2 thùng \(X\) và \(Y\).
• Lưu ý: \(N\) không xuất hiện trong input, tuy nhiên, \(X, Y \leq N \leq 10000\)

Output

• Với mỗi yêu cầu dạng X Y 2 (với \(Z = 2\)) bạn cần ghi ra số 0 hoặc 1 trên 1 dòng tùy thuộc 2 thùng \(X\) và \(Y\) không thuộc hoặc thuộc cùng một nhóm bình.

Scoring

• \(1 ≤ N ≤ 10000\)
• \(1 ≤ P ≤ 50000\)

Example

Có \(n\) thành phố và \(m\) con đường giữa chúng. Thật không may, tình trạng của các con đường quá tệ đến nỗi chúng không thể đi được. Nhiệm vụ của bạn là sửa chữa một số con đường để có một tuyến đường đàng hoàng giữa hai thành phố bất kỳ.

Đối với mỗi con đường, bạn biết chi phí sửa chữa của nó, và bạn nên tìm một giải pháp trong đó tổng chi phí nhỏ nhất có thể.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và con đườ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 dòng có ba số nguyên \(a\), \(b\) và \(c\): có một con đường giữa thành phố \(a\) và \(b\), chi phí sửa chữa của nó là \(c\). Tất cả con đường đều là con đường hai chiều
• Mỗi con đường nối những cặp thành phố khác nhau, và có nhiều nhất một con đường giữa hai thành phố bất kì

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2\cdot 10^5\)
• \(1 \leq a, b \leq n\)
• \(1 \leq c \leq 10^9\)

Output

• In một số nguyên: tổng chi phí sửa chữa tối thiểu. Tuy nhiên, nếu không có giải pháp, hãy in IMPOSSIBLE

Example

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

14

Nước Anpha đang lập kế hoạch xây dựng một thành phố mới và hiện đại. Theo kế hoạch, thành phố sẽ có \(N\) vị trí quan trọng, được gọi là \(N\) trọng điểm và các trọng điểm này được đánh số từ 1 tới \(N\). Bộ giao thông đã lập ra một danh sách \(M\) tuyến đường hai chiều có thể xây dựng được giữa hai trọng điểm nào đó. Mỗi tuyến đường có một thời gian hoàn thành khác nhau.

Các tuyến đường phải được xây dựng sao cho \(N\) trọng điểm liên thông với nhau. Nói cách khác, giữa hai trọng điểm bất kỳ cần phải di chuyển được đến nhau qua một số tuyến đường. Bộ giao thông sẽ chọn ra một số tuyến đường từ trong danh sách ban đầu để đưa vào xây dựng sao cho điều kiện này được thỏa mãn.

Do nhận được đầu tư rất lớn từ chính phủ, bộ giao thông sẽ thuê hẳn một đội thi công riêng cho mỗi tuyến đường cần xây dựng. Do đó, thời gian để hoàn thành toàn bộ các tuyến đường cần xây dựng sẽ bằng thời gian lâu nhất hoàn thành một tuyến đường nào đó.

Yêu cầu: Giúp bộ giao thông tính thời gian hoàn thành các tuyến đường sớm nhất thỏa mãn yêu cầu đã nêu.

Input

• Dòng chứa số \(N\) và \(M\) (\(1 ≤ N ≤ 1000; 1 ≤ M ≤ 10000\)).
• \(M\) tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(t\) cho biết có thể xây dựng tuyến đường nối giữa trọng điểm \(u\) và trọng điểm \(v\) trong thời gian \(t\). Không có hai tuyến đường nào nối cùng một cặp trọng điểm.

Output

• Một số nguyên duy nhất là thời gian sớm nhất hoàn thành các tuyến đường thỏa mãn yêu cầu đã nêu.

Example

Nguồn: SPOJ

\(N\) con bò của Farmer John (\(1 \leq N \leq 1000\)) muốn tổ chức một hệ thống "moo-cast" khẩn cấp để truyền những thông điệp quan trọng cho nhau.

Thay vì rống gọi nhau từ xa, đàn bò quyết định tự trang bị bộ đàm, mỗi con một chiếc. Mỗi bộ đàm có bán kính truyền hữu hạn, nhưng đàn bò có thể chuyển tiếp thông điệp cho nhau theo một đường đi gồm nhiều chặng, nên không nhất thiết mọi con bò đều phải truyền trực tiếp được tới mọi con bò khác.

Đàn bò cần quyết định sẽ chi bao nhiêu tiền cho các bộ đàm. Nếu chúng chi \(X\) đô la, mỗi con sẽ nhận được một bộ đàm có khả năng truyền xa tới khoảng cách \(\sqrt{X}\). Nói cách khác, bình phương khoảng cách giữa hai con bò phải không vượt quá \(X\) để chúng có thể liên lạc.

Hãy giúp đàn bò xác định giá trị nguyên nhỏ nhất của \(X\) sao cho một thông điệp phát từ bất kỳ con bò nào cuối cùng cũng có thể tiếp cận mọi con bò khác.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\) và \(y\) của một con bò. Cả hai tọa độ đều là số nguyên trong khoảng \(0 \ldots 25\,000\).

Dữ liệu ra

In một dòng chứa số nguyên \(X\), là số tiền tối thiểu đàn bò phải chi cho các bộ đàm.

Ví dụ

4
1 3
5 4
7 2
6 1

17

Nguồn

USACO 2016 December Contest, Gold — Moocast. Tác giả đề: Richard Peng.

https://usaco.org/index.php?page=viewproblem2&cpid=669

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

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2\cdot 10^5\)
• \(1 \leq a, b \leq n\)

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

Mạng lưới của Syrjälä có \(n\) máy tính và \(m\) kết nối giữa chúng. Mạng lưới gồm các thành phần các máy tính có thể gửi tin nhắn cho nhau.

Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì lý do này, nếu một kết nối gặp sự cố, sẽ không ai sửa nó. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.

Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.

Input

• Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\): số lượng máy tính, kết nối và sự cố. Các máy tính được đánh số \(1,2,...,n\)
• Tiếp theo là \(m\) dòng mô tả các kết nối. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một kết nối giữa hai máy \(a\) và \(b\). Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy
• Cuối cùng là \(k\) dòng mô tả các sự cố. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): kết nối giữa hai máy \(a\) và \(b\) gặp sự cố

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2\cdot 10^5\)
• \(1 \leq k \leq m\)
• \(1 \leq a,b \leq n\)

Output

• Sau mỗi sự cố, in ra số lượng thành phần.

Example

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

2 2 3

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có \(N\) hành tinh được biểu diễn như các điểm trong không gian 3 chiều. Chi phí phải chi cho việc nối giữa hành tinh \(A\) và hành tinh \(B\) là \(min\){ |\(x_A - x_B\)|, |\(y_A - y_B\)|, |\(z_A\) - \(z_B\)| } với (\(x_A\), \(y_A\), \(z_A\)), (\(x_B\), \(y_B\), \(z_B\)) là tọa độ của hành tinh \(A\), \(B\) trong không gian 3 chiều.

Đế chế dự tính sẽ xây dựng \(N – 1\) cầu nối như vậy để các hành tinh liên thông với nhau và chi phí để trả sao cho phải nhỏ nhất có thể.

Input

• Dòng đầu là số hành tinh \(N\).
• N dòng sau mỗi dòng là tọa độ của một hành tinh.

Output

• Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.

Example

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

4