Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

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

Output 1:

3 2 1

Input 2:

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

Output 2:

1 1 -1

Cho đồ thị vô hướng, gồm ~n~ đỉnh và ~m~ cạnh, mỗi đỉnh sẽ có một trọng số.

Hãy tìm một đường đi từ ~1~ tới ~n~ sao cho chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi là nhỏ nhất có thể.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le 2*10^5)~
• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên dương ~c_i~ là trọng số của đỉnh thứ ~i~ ~(1 \le c_i \le 10^9)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~.

Output:

• In ra chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi sao cho nó nhỏ nhất có thể.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

3 3
1 2 3
1 2
2 3
1 3

Output 1

1

Explanation 1:

Đi đường ~(1,2,3)~ thay vì ~(1,3)~.

Năm ~1976~, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

• Không có khuyên.
• Đồ thị vô hướng.
• Đồ thị liên thông.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ ~0~ tới ~n-1~.
  • Dòng thứ hai gồm số nguyên dương ~m~ miêu tả số cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u,v~ miêu tả cạnh ~(u,v)~.

Output

• Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

• ~1 \le t \le 20~
• ~1 \le n,m \le 200~

Sample Input 1:

3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

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

Sample Output 1:

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

Romeo và Juliet cuối cùng đã quyết định kết hôn. Nhưng việc chuẩn bị tiệc cưới diễn ra không được suôn sẻ cho lắm, vì ai cũng biết rằng quan viên hai họ: Montesco và Capuleto có mối thù sâu đậm. Bạn sẽ cần phải chọn xem nên mời người nào và không nên mời người nào để ngăn chặn những mâu thuẫn.

Bạn sẽ có một danh sách ~n~ người có thể được mời đến bữa tiệc hoặc không. Với người thứ ~i~, bạn lại có danh sách các kẻ thù của người đó: ~e_1, e_2, ..., e_{p_i}~.

Mối quan hệ thù hằn này có hai tính chất như sau:

• Nếu ~a~ là kẻ thù của ~b~, và ~b~ là kẻ thù của ~c~ thì ~a~ là bạn của ~c~. Đồng thời kẻ thù của ~c~ cũng sẽ trở thành kẻ thù của ~a~.
• Nếu ~a~ là kẻ thù của ~b~ thì ~b~ cũng là kẻ thù của ~a~ (kể cả khi ~a~ không nằm trong danh sách kẻ thù trực tiếp của ~b~).

Một người sẽ chỉ chấp nhận tới dự đám cưới khi và chỉ khi tất cả bạn bè của anh ta được mời và tất cả kẻ thù của anh ta đều không tham dự.

Nhiệm vụ của bạn là tối đa hóa số người có thể được mời.

Ví dụ, nếu ~n = 5~ và ta biết rằng: ~1~ là kẻ thù của ~3~, ~2~ là kẻ thù của ~1~ và ~4~ là kẻ thù của ~5~, như vậy ta có thể mời tối đa 3 người. Những người này có thể là ~2, 3~ và ~4~.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số người cần được xem xét.
  • ~n~ dòng sau, dòng thứ ~i~: đầu tiên có một số nguyên ~p~ miêu tả số kẻ thù trực tiếp mà người thứ ~i~ có, sau đó là ~p~ số nguyên dương miêu tả kẻ thù của người thứ ~i~.

Output

• Với mỗi test case, in ra số lượng người lớn nhất có thể mời.

Constraints

• ~1 \le t \le 20~
• ~1 \le k < n\le 200~.

Sample Input 1:

3
5
1 3
1 1
0
1 5
0
8
2 4 5
2 1 3
0
0
0
1 3
0
1 5
3
2 2 3
1 3
1 1

Sample Output 1:

3
5
0

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1

Đất nước U có ~n~ thành phố, đánh số từ 1 đến ~n~. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng ~b~ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng U đã chọn ra ~r~ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

• Dòng thứ nhất gồm bốn số nguyên: ~n,m,b,r\ (2 \le n \le 5.10^5; 1 \le m \le 5.10^5; 1 \le b,r \le n)~
• Dòng thứ hai gồm ~b~ số nguyên là chỉ số của các thành phố được đặt kho lương thực;
• Dòng thứ ba gồm ~r~ số nguyên là chỉ số của các thành phố được đặt trại quân sự;
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~ thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố ~u~ và ~v~.

Output

• Xuất ra ~r~ số nguyên trên cùng một dòng là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu.

Subtask

• Subtask 1: (40% số test): ~n \le 5000~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1 2 1

Explanation 1

• Thành phố ~1~: ~1 → 2~
• Thành phố ~4~: ~4 → 3~
• Thành phố ~5~: ~5 → 4 → 3~

Cho một cây vô hướng không trọng số gồm ~n~ đỉnh.

Với mọi ~1 \le u < v \le n~, gọi ~S(u,v)~ là tập các cạnh nằm trong đường đi ngắn nhất từ ~u~ tới ~v~.

Với mỗi cạnh ~(x,y)~ của cây, hãy đếm xem cạnh đó xuất hiện trong bao nhiêu tập ~S(u,v)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

• ~1 \le n \le 10^5~

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• In ra kết quả cần tính của mỗi cạnh ~(x,y)~ theo thứ tự Input.

Sample Input 1:

4
1 2
1 3
3 4

Sample Output 1:

3
4
3

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~w_i~.

Chắc hẳn các bạn đều biết khái niệm về cây con, giả sử ta có một cây có gốc là ~1~ như sau:

• Cây con có gốc là ~2~ sẽ bao gồm các đỉnh : ~\{2,6,5,4\}~.
• Cây con có gốc là ~3~ sẽ bao gồm các đỉnh : ~\{3\}~.

Ta định nghĩa ~S(root,a)~ là tổng trọng số các đỉnh trong cây con gốc ~a~ khi gốc của cây là ~root~. Hay ~S(root,a) = \sum_u^{u \in subtree(a)} w[u]~ khi gốc của cây là ~root~.

Bạn cần trả lời ~q~ câu hỏi, mỗi câu hỏi có dạng như sau:

• ~a~ ~b~ : Hãy in ra ~S(a,b)~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(n,q \le 2 \times 10^5)~ miêu tả số đỉnh và số truy vấn.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~w~ ~(1 \le w_i \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n)~ miêu tả truy vấn tương ứng.

Output:

• Với mỗi truy vấn, in ra đáp án tương ứng.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n,q \le 2000~
• Subtask ~2~ (~25\%~ số điểm): ~a_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~25\%~ số điểm): ~b_i = 1~ với mọi truy vấn.
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

10
6
12
3

Explanation 1

Đối với hai truy vấn đầu tiên, gốc của cây bằng ~1~.

• ~S(1,2) = w[2] + w[6] + w[5] + w[4] = 10~
• ~S(1,6) = w[6] + w[5] = 6~

Đối với truy vấn thứ ba, gốc của cây bằng ~4~:

• ~S(4,2) = w[2] + w[6] + w[5] + w[1] + w[3] = 12~

Đối với truy vấn thứ tư, gốc của cây bằng ~2~

• ~S(2,1) = w[1] + w[3] = 3~

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~a_i~. Lưu ý dãy ~a~ gồm các phần tử đôi một khác nhau.

Bạn được nhận thêm hai giá trị nguyên không âm ~c~ và ~d~. Xét một đường đi đơn ~P~ trên cây, gọi ~V~ là tập đỉnh trên đường đi này. Chúng ta định nghĩa độ đẹp của ~P~ là: ~ c \times mex_{x \in V} \{a_x\} + d \times max_{x \in V} \{a_x\} ~

Hãy tìm độ đẹp lớn nhất của tất cả các đường đi đơn.

PS: ~mex~ ~V~ là số nguyên không âm nhỏ nhất không xuất hiện trong tập ~V~, ~max~ ~V~ là số lớn nhất trong tập ~V~.

Input:

• Dòng đầu tiên gồm hai ba số nguyên ~n~ ~(1 \le n \le 10^5, 0 \le c,d \le 10^9)~.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~ ~(0 \le a_i \le n-1)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.

Output:

• In ra đáp án cần tìm.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n \le 200~
• Subtask ~2~ (~25\%~ số điểm): ~n \le 2000~
• Subtask ~3~ (~25\%~ số điểm): ~d = 0~
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

25

Trong buổi phỏng vấn xin việc vào vị trí kiến trúc sư mạng, bộ phận tuyển dụng đưa cho bạn câu hỏi như sau:

Hệ thống máy tính của công ty gồm ~n~ máy tính, máy thứ ~i~ (~1 \leq i \leq n~) có ~c_i~ cổng kết nối. Các máy tính được chia thành ~k~ trạm, trạm thứ ~j~ (~1 \leq j \leq k~) có ~x_j~ máy tính, mỗi máy tính thuộc đúng một trạm.

Có ~m~ yêu cầu dạng ~(u,v)~: Mỗi máy trong trạm ~u~ muốn liên lạc với từng máy trong trạm ~v~. Ta cần thiết kế đường truyền tin giữa các trạm máy tính khác nhau, bằng cách thiết lập kết nối hai chiều giữa các cặp hai máy bất kì sao cho thỏa mãn ~m~ yêu cầu trên và số kết nối của mỗi máy không được vượt quá số cổng kết nối của máy đó. Biết rằng để máy này truyền được tin tới máy khác, có thể truyền trực tiếp hoặc gián tiếp qua một số máy trung gian nào đó.

Để đánh giá mức độ hiệu quả của mạng, người ta định nghĩa hàm ~f~:

• Giả sử tổng số kết nối là ~E~.
• Định nghĩa độ trễ mạng ~L~ như sau: xét cặp máy ~(x,y)~ (~x \neq y~) bất kì, mà ~x~ có đường truyền đến ~y~. Đặt ~d(x,y)~ là đường truyền ngắn nhất (đi qua ít kết nối nhất) giữa hai máy này. Độ trễ ~L~ của hệ thống sẽ là ~\max(d(x,y))~ trong mọi cặp ~(x,y)~ đó.
• Khi đó: ~f = E \cdot n + L~.

Hãy thiết kế một hệ thống mạng có ~f~ nhỏ nhất.

PS: HNOJ đang lỗi checker nên các bạn chỉ cần in ra giá trị ~f~

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~m~ (~1 \leq k \leq n \leq 10 ^ 5~, ~1 \leq m \leq \min(k^2, 10^5)~) lần lượt là số máy, số trạm và số yêu cầu.
• Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~2 \leq c_i \leq n~) là số lượng cổng kết nối của mỗi máy.
• Tiếp theo là ~k~ nhóm dòng mô tả các trạm máy tính ~1,2,3,\ldots,k~:
  • Dòng đầu tiên chứa số nguyên ~x_j~ là số lượng máy của trạm thứ ~j~.
  • Dòng tiếp theo chứa ~x_j~ số nguyên là số hiệu của các máy.
  • Dữ liệu vào đảm bảo ~x_1 + x_2 + \ldots + x_k = n~ và số hiệu của mỗi máy khác nhau đôi một và tạo thành một hoán vị của ~\{1,2,3,\dots,n\}~.
• Trong ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ (~1 \le u,v \le k~) cho biết yêu cầu giữa hai trạm ~u~ và ~v~.

Output

• Dòng đầu tiên in ra số nguyên ~f~.
• Nếu ~E \leq 10^5~, in ra các cặp kết nối theo định dạng u v trong ~E~ dòng tiếp theo.

Nếu có nhiều cách nối khác nhau, bạn hãy in ra 1 cách nối bất kì. Chứng minh được luôn tồn tại cách nối các máy thỏa mãn các yêu cầu với giới hạn của đề bài.

Subtask

• Subtask ~1~ (~30\%~ số điểm): ~n \le 6~.
• Subtask ~2~ (~30\%~ số điểm): ~c_i = n \ \forall 1 \leq i \leq n~.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 3 2
3 3 3 
1
2
1
3
1
1
2 1
2 3

Sample Output 1

8
3 2
2 1

Explanation 1

Trạm ~2~ có thể truyền tin cho trạm ~3~ thông qua đường truyền sau: trạm ~2~ ~\rightarrow~ trạm ~1~ ~\rightarrow~ trạm ~3~ (tương ứng với các máy ~3,2,1~).

Sample Input 2

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

Sample Output 2

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

Explanation 2

Đây là bản vẽ thiết kế hệ thống mạng máy tính theo đầu ra trên: