Bài tập

BT đang chơi một trò chơi gọi là "Nền văn minh". Bạn hãy giúp BT chơi trò chơi đó.

Trò chơi có \(n\) thành phố và \(m\) con đường vô hướng. Các thành phố được đánh số từ \(1\) đến \(n\). Giữa hai thành phố bất kỳ hoặc có một đường đi duy nhất hoặc không có đường đi nào cả. Một đường đi là một dãy các thành phố khác nhau \(v_1, v_2, ..., v_k\) sao cho giữa hai thành phố liên tiếp \(v_i\) và \(v_{i+1}\) \((1 \leq i < k)\) có một con đường nối chúng. Chiều dài của đường đi này bằng \(k-1\).

Chúng ta nói rằng hai thành phố cùng một vùng khi và chỉ khi có đúng một đường đi kết nối hai thành phố này.

BT muốn trả lời hai loại truy vấn sau:

• "1 x": Tìm chiều dài đường đi dài nhất trong vùng chứa thành phố \(x\).
• "2 x y": Kiểm tra xem thành phố \(x\) và thành phố \(y\) có cùng một vùng hay không. Nếu không, BT cần phải hợp nhất hai vùng như sau: chọn một thành phố trong vùng thứ nhất và một thành phố trong vùng thứ hai, nối chúng bằng một con đường sao cho chiều dài của đường đi dài nhất trong vùng hợp nhất là nhỏ nhất có thể. Nếu có nhiều cách làm như vậy, bạn được phép chọn một cách bất kỳ.

Bạn hãy giúp BT trả lời các câu hỏi loại 1 và thực hiện các yêu cầu loại 2.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) \((1 \leq n \leq 3 \times 10^5; 0 \leq m \leq n; 1 \leq q \leq 3 \times 10^5)\) --- số thành phố, số con đường ban đầu và số truy vấn.
• Mỗi trong số \(m\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq n, a_i \neq b_i)\) --- mô tả một con đường nối hai thành phố \(a_i\) và \(b_i\). Có thể có nhiều nhất một con đường nối hai thành phố.

• Mỗi trong số \(q\) dòng tiếp theo chứa một truy vấn thuộc một trong hai dạng:

• "1 x": Xác định chiều dài của đường đi dài nhất trong vùng chứa thành phố \(x\) \((1 \leq x \leq n)\). Dữ liệu đảm bảo luôn có ít nhất một truy vấn dạng này.

• "2 x y": Hợp nhất vùng của thành phố \(x\) và vùng của thành phố \(y\) \((1 \leq x, y \leq n, x \neq y)\).

Output

Với mỗi câu hỏi dạng thứ nhất, in ra kết quả trên một dòng.

Example

10 3 9
1 2
1 3
2 4
1 2
2 1 1
2 7 9
2 3 2
2 2 7
2 2 5
1 6
2 7 4
1 7

3
0
4

Trên một hòn đảo có \(N\) ngôi làng, mỗi làng ban đầu yêu thích một màu cà vạt khác nhau. Làng thứ \(i\) có \(s_i\) người. Giữa các làng có \(M\) con đường hai chiều nối trực tiếp một số cặp làng.

Theo thời gian, mỗi tuần một làng có thể thuyết phục một làng láng giềng đổi sang màu cà vạt của mình. Việc này chỉ xảy ra nếu tổng số người yêu thích màu cà vạt của làng đi thuyết phục nhiều hơn hoặc bằng tổng số người yêu thích màu của làng bị thuyết phục. Ban đầu, mỗi làng chỉ có dân trong làng mình ủng hộ màu cà vạt của chính họ.

Quá trình thuyết phục tiếp tục cho đến khi tất cả người dân trên đảo đều yêu thích cùng một màu cà vạt.

Bạn cần xác định: màu cà vạt ban đầu của những làng nào có thể trở thành màu cà vạt duy nhất cuối cùng của toàn đảo.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 200\,000\), \(0 \le M \le 200\,000\)) --- số làng và số con đường.
• Dòng thứ hai chứa \(N\) số nguyên \(s_1, s_2, \ldots, s_N\) (\(1 \le s_i \le 10^9\)) --- dân số mỗi làng.
• Mỗi trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le N\), \(a \ne b\)) --- mô tả một con đường nối làng \(a\) và \(b\).

Đảm bảo rằng toàn bộ các làng tạo thành một đồ thị liên thông.

\OutputFile

In ra một chuỗi nhị phân có \(N\) ký tự. Ký tự thứ \(i\) là 1 nếu màu cà vạt của làng \(i\) có thể trở thành màu cà vạt chung cuối cùng, ngược lại in 0.

\Examples

\beginexample
\exmp4 4
2 2 4 3
1 2
1 3
2 3
3 4
1110

\endexample

\Scoring

• Subtask 1 (15 điểm): \(N \le 2\,000\), \(M \le 2\,000\)
• Subtask 2 (15 điểm): \(s_1 \ge s_2 \ge \cdots \ge s_N\), và đồ thị có dạng cây. Khi đặt gốc của cây là \(1\), khi tổ tiên của một đỉnh \(u\) bất kỳ là \(p\) thì (\(1 \le p \lt u \le n\)).
• Subtask 3 (15 điểm): Các làng được nối nếu và chỉ nếu \(|a - b| = 1\)
• Subtask 4 (30 điểm): Có tối đa 10 giá trị dân số khác nhau
• Subtask 5 (25 điểm): Không có giới hạn gì thêm

Note

Giải thích ở test ví dụ đề bài:

Số đầu tiên được ghi là số 1 bởi vì làng 1 có thể là làng có màu kết thúc -- ta có quá trình như sau: Làng 1 bắt đầu với việc thuyết phục làng 2 (lúc này số người yêu thích màu của các làng là 2 và 2). Sau khi thuyết phục số người yêu thích màu của làng 1 là 4. Tiếp theo thuyết phục làng 3 (hiện giờ số người yêu thích màu của các làng là \(4\) và \(4\)). Số người yêu thích màu 1 trở thành 8. Cứ như vậy thuyết phục thêm làng thứ 4.

Bạn có một nhân vật cần được tăng chỉ số sức mạnh.

Nhân vật có \(N\) kỹ năng, được đánh số từ \(1\) đến \(N\).
Kỹ năng thứ \(i\) có hai chỉ số tăng tiến là \(s_i\) và \(e_i\).

• Lần đầu tiên tăng cấp kỹ năng \(i\), nhân vật nhận được \((s_i + e_i)\) điểm sức mạnh.
• Từ lần tăng cấp thứ hai trở đi của kỹ năng \(i\), mỗi lần chỉ nhận thêm \(e_i\) điểm sức mạnh.

Bạn có thể tăng cấp một kỹ năng bất kỳ, không giới hạn số lần.

Trò chơi diễn ra trong \(M\) phút. Mỗi phút, nhân vật được thực hiện đúng một lần tăng cấp.

Yêu cầu:
Hãy tính chỉ số sức mạnh lớn nhất mà nhân vật có thể đạt được sau \(M\) phút.

\InputFile
\begin itemize

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

• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(s_i\) và \(e_i\) \((1 \le s_i, e_i \le 10^9)\).

\OutputFile
In ra một số nguyên duy nhất là chỉ số sức mạnh lớn nhất có thể đạt được.

Subtasks

• Subtask 1 (40 điểm): \(M = 2\).
• Subtask 2 (40 điểm): \(M \le 100\).
• Subtask 3 (20 điểm): Không có ràng buộc thêm.

Example

3 4
2 2
2 5
5 1

23

Cho một cây gồm \(n\) đỉnh. Với mỗi đỉnh \(i\), ta biết hai giá trị:

• \(c_i\): giá trị của đỉnh nếu được tô màu đỏ;
• \(p_i\): giá trị của đỉnh nếu được tô màu xanh.

Xét đường đi ngắn nhất từ một đỉnh \(A\) đến một đỉnh \(B\) trên cây. Khi duyệt theo thứ tự các đỉnh trên đường đi, mỗi đỉnh được chọn một trong hai màu: đỏ hoặc xanh.

Một đường đi được gọi là hài hòa nếu trong suốt quá trình duyệt đường đi, tại mọi thời điểm, không màu nào "áp đảo" màu còn lại. Cụ thể, màu đỏ hoặc xanh được coi là áp đảo nếu nó xuất hiện ít nhất 3 lần nhiều hơn màu còn lại.

Giá trị của đường đi là tổng các giá trị nhận được từ các đỉnh theo màu được chọn.

Với mỗi truy vấn gồm hai đỉnh \(u\) và \(v\), hãy tìm giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\). Đảm bảo rằng luôn tồn tại ít nhất một cách tô hợp lệ.

\InputFile
\begin itemize

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(c_i\) (\(-10^9 \le c_i \le 10^9\)).

• Dòng thứ ba chứa \(n\) số nguyên \(p_i\) (\(-10^9 \le p_i \le 10^9\)).

• Tiếp theo là \(n-1\) dòng, mỗi dòng chứa hai số \(u\) và \(v\) biểu thị một cạnh của cây.

• Tiếp theo là \(q\) dòng, mỗi dòng chứa hai số \(u, v\) --- truy vấn cần trả lời.

\OutputFile

Với mỗi truy vấn, in ra giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\).

\Scoring

• Subtask 1 (15 điểm): \(n, q \le 15\).
• Subtask 2 (34 điểm): \(n, q \le 1000\).
• Subtask 3 (19 điểm): \(q \le 1000\).
• Subtask 4 (32 điểm): Không có ràng buộc bổ sung.

Example

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

-3
1
3

5 3
-4 0 -5 -5 5
5 5 -4 2 2
1 5
2 3
3 4
1 3
5 4
2 5
2 4

8
10
2