Hãy biễu diễn đồ thị đã cho theo dạng ma trận kề.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~, ~m~.

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ tương ứng là có cung nối giữa ~u~ và ~v~.

Dữ liệu ra:

• Ghi ra ma trận kề biễu diễn cho đồ thị.

Ràng buộc:

• ~1 \le n,m \le 100~

Ví dụ:

Input

4 4 
1 2 
1 3 
1 4 
2 3 

Output

0 1 1 1 
1 0 1 0 
1 1 0 0 
1 0 0 0

Hãy biễu diễn đồ thị đã cho theo dạng ma trận kề.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~, ~m~.

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ tương ứng là có cung nối giữa ~u~ và ~v~.

Dữ liệu ra:

• Ghi ra ma trận kề biễu diễn cho đồ thị.

Ràng buộc:

• ~1 \le n,m \le 100~

Ví dụ:

Input

4 4 
1 2 
1 3 
1 4 
2 3 

Output

0 1 1 1  
0 0 1 0  
0 0 0 0  
0 0 0 0  

Cho đồ thị có ~N~ đỉnh và ~M~ cạnh, nhiệm vụ của bạn là đưa ra thứ tự duyệt rộng của đồ thị với đỉnh xuất phát là đỉnh 1.

Dữ liệu vào:

• Dòng đầu tiên là hai số ~N~, ~M~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ tương ứng có cung nối giữa hai đỉnh ~u~,~v~.

Dữ liệu ra:

• Ghi ra thứ tự duyệt rộng xuất phát từ đỉnh 1

Ràng buộc

• ~1 \le N,M \le 100~

• ~1 \le u,v \le 100~

Ví dụ:

Input:

4 4 
1 2 
1 4 
2 3 
3 4 

Output:

1 2 4 3

Cho một cây gồm ~N~ nút và ~N-1~ cung, các nút được đánh số từ 1 đến ~N~. Nút gốc nằm ở mức 1. Nhiệm vụ của bạn là đếm số lượng nút ở mức ~x~.

INPUT:

• Dòng đầu tiên chứa số nguyên ~N~ là số lượng nút.

• ~N-1~ dòng tiếp theo chứa hai số nguyên ~u~,~v~ tương ứng là có cung nối từ ~u~ đến ~v~.

• Dòng tiếp theo chứa số nguyên ~x~.

OUTPUT:

• Ghi ra số lượng nút ở mức ~x~.

Ràng buộc:

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

• ~1 \le a,b \le N~

Ví dụ:

Input

11 1 
1 2 
13 3 
15 4 
17 5 
11 6 
2 7 
1 8 
15 9 
4 10 
15 12 
5 13 
2 14 
17 15 
15 16 
11 17 
15 18 
9 19 
16 20 
2

Output:

3

Cho ~N~ hòn đảo (đánh số từ 1 đến ~N~) được nối với nhau bởi ~M~ cây cầu. John là một người rất yêu thể thao nhưng lại ngại qua cầu. Bạn hãy giúp John tìm đường đi từ đảo thứ 1 đến đảo thứ ~N~ sao cho đi qua ít cây cầu nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~T~

Với mỗi test case

• Dòng đầu tiên chứa hai số nguyên ~N~, ~M~.

• ~M~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~X~, ~Y~. Kí hiệu rằng có cây cầu nối giữa hai đảo ~X~ và ~Y~.

Dữ liệu ra:

• Với mỗi test case ghi ra file BISLAND.OUT một số nguyên là số lượng cây cầu tối thiểu trên đường đi từ đảo 1 đến đảo N, mỗi kết quả trên 1 dòng.

Ràng buộc:

• ~1 ≤ T ≤ 10~

• ~1 ≤ N ≤ 10^4~

• ~1 ≤ M ≤ 10^5~

• ~1 ≤ X, Y ≤ N~

Ví dụ:

Input:

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

Output:

2 
2 

Bạn được cho một bản đồ quân sự có ~N~ hàng và ~M~ cột. Tại hàng ~i~, cột ~j~ chứa một giá trị (~i~,~j~) chứa giá trị 0 hoặc 1 tương ứng là không có quân địch hoặc có quân địch. Quân của bạn chỉ còn 1 quả đại bác duy nhất nên bạn cần tìm cách tiêu diệt được số quân địch lớn nhất. Biết rằng đại bác bắn đi sẽ tiêu diệt được 1 nhóm quân có liên thông với nhau. Hai quân lính được xem là liền kề nếu nó liền kề với 8 ô quanh nó.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ testcase Với mỗi bộ test case.

• Dòng thứ 2 chứa hai số nguyên ~N~ và ~M~

• Tiếp theo là ma trận có ~N~ hàng và ~M~ cột chứa giá tri 0 hoặc 1 là mô tả cho bản đồ.

Dữ liệu ra:

• Với mỗi bộ test, ghi ra 2 số nguyên ~X~ và ~Y~ tương ứng là số nhóm quân đội và số lượng quân nhiều nhất có thể chết khi bắn quả đại bác cuối cùng.

Ràng buộc:

• ~1 ≤ T ≤ 10~

• ~1 ≤ N,M ≤ 1000~

Ví dụ:

Input:

2 
4 6 
0 0 0 1 1 0  
1 1 0 0 0 0  
0 1 0 0 0 0  
0 0 1 0 0 0  
6 4 
1 1 1 1  
0 0 0 0  
0 1 0 0  
1 0 1 0  
1 0 0 0  
1 0 0 0

Output:

2 4 
2 5

~H~ là một cô gái rất xinh đẹp, trong một buổi tiệc rất nhiều chàng trai muốn nhảy với ~H~, danh sách chàng trai được đánh số từ 1 đến ~N~. Cho biết danh sách những đôi được nhảy với nhau, bạn hãy xác định độ may mắn của các chàng trai. Biết rằng độ may mắn được tính dựa vào việc chàng trai có được trực tiếp nhảy với H hay không? Nếu nhảy trực tiếp độ may mắn là 1, nếu không được nhảy trực tiếp nhưng lại nhảy với người được nhảy với H sẽ có độ may mắn là 2, tương tự như vậy với các độ may mắn khác. Nếu chàng trai không được nhảy với ~H~ cũng như tập những người may mắn được nhảy với H sẽ xem như không may mắn và nhận giá trị -1.

Lưu ý: ~H~ được đánh số là 0

Input:

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~ tương ứng là số người trong bữa tiệc và số lượng đôi nhảy với nhau.

• M dòng tiếp theo, mỗi dòng là hai giá trị ~x~,~y~ tương ứng là hai người ~x~,~y~ đã nhảy với nhau.

Output:

• Ghi ra N-1 dòng, tại dòng thứ i là độ may mắn của người thứ i.

Ràng buộc:

• N<=1000 • ~M <=(N*(N-1))/2~

Ví dụ:

Input:

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

Output:

1 
1 
2 
2 

Cho đồ thị có ~N~ đỉnh và ~M~ cạnh, nhiệm vụ của bạn là đưa ra thứ tự duyệt sâu của đồ thị với đỉnh xuất phát là đỉnh 1.

Input:

• Dòng đầu tiên là hai số ~N~, ~M~.

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ tương ứng có cung nối giữa hai đỉnh ~u~,~v~.

Output:

• Ghi ra thứ tự duyệt rộng xuất phát từ đỉnh 1.

Ràng buộc:

• ~1 \le N,M \le 100~

• ~1 \le u,v \le 100~

Ví dụ:

Input:

4 4 
1 2 
1 4 
2 3 
3 4

Output:

1 2 3 4

Cho đồ thị có ~N~ đỉnh, ~M~ cạnh và nút ~x~. Nhiệm vụ của bạn là đếm số lượng nút không liên thông với nút ~x~.

Input:

• Dòng đầu tiên là hai số ~N~, ~M~. • ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ tương ứng có cung nối giữa hai đỉnh ~u~,~v~. • Dòng cuối cùng là số nguyên ~x~.

Output:

• Ghi ra số lượng nút không liên thông với ~x~.

Ràng buộc:

• ~1 \le N,M \le 10^5~

• ~1 \le x \le N~

Ví dụ:

Input:

4 4 
1 2 
1 4 
2 3 
3 4 

Output:

0 

Thành là một thanh niên cao to và đẹp trai, với vẻ ngoài điển trai đã khiến rất nhiều cô gái phải chết mê chết mệt. Cho biết bản đồ khu vực của Thành đang sống gồm ~N~ thành phố được nối với nhau bởi ~N-1~ tuyến đường. Thành đang ở thành phố có số thứ tự 1, có thể xem bản đồ như dạng cây với thành phố Thành đang sống là gốc. Có ~Q~ cô gái say đắm trước vẻ nam tính của Thành. Thành là người ngại vận động nên anh muốn tìm người bạn gái ở gần mình nhất, khoảng cách giữa hai thành phố chính là số đoạn đường phải đi qua giữa hai thành phố. Bạn hãy giúp Thành tìm ra số thứ tự của thành phố mà cô gái thõa mãn điều kiện đang sống.

Input:

• Dòng đầu tiên chứa số nguyên ~N~ là số thành phố

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~,~v~ mô tả tồn tại đường đi giữa hai thành phố ~u~ và ~v~.

• Dòng tiếp theo chứa số nguyên ~Q~ là số cô gái

• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên là số thứ tự của thành phố mà cô gái thứ i đang sống.

Output:

• Ghi ra một số nguyên duy nhất là số thứ tự của thành phố mà cô gái thõa mãn đang sống. Nếu có nhiều cô gái cùng thõa mãn điều kiện về khoảng cách thì sẽ ưu tiên cô gái có số thứ tự thành phố nhỏ hơn. Biết rằng không có cô gái nào sống ở thành phố 1 và không có hai cô gái sống chung một thành phố.

Ràng buộc:

• ~2 \le N \le 1000~

• ~1 \le u,v \le =N~

• ~1 \le Q \le (N-1)~

Ví dụ:

Input:

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

Output:

3

Cho một cây có ~N~ đỉnh và ~M~ cạnh, đỉnh được gọi là hạnh phúc nếu nó có số cây con lớn hơn nút cha. Nhiệm vụ của bạn là đếm xem trên cây có bao nhiêu đỉnh hạnh phúc.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X~ và ~Y~ mô tả có cạnh nối giữa hai đỉnh ~X~ và ~Y~.

Output

• Ghi ra một số nguyên duy nhất là số đỉnh hạnh phúc.

Ràng buộc

• ~1≤N≤100000~

• ~0≤M≤N-1~

• ~1≤X,Y≤N~

Ví dụ:

Input

4 3 
1 2 
2 3 
2 4 

Output

1

Cho một cây với ~N~ nút, nút thứ i được gán một giá trị ~val[i]~. Cho ~Q~ truy vấn với mỗi truy vấn có dạng ~X~ ~K~. Với mỗi truy vấn, bạn phải tìm đường đi xuất phát từ nút ~X~ sao cho tổng các nút trên đường đi phải lớn hơn hoặc bằng ~K~ và số lượng nút trên đường đi phải đảm bảo là ít nhất. Nếu tồn tại đường đi thõa mãn yêu cầu thì in ra số lượng nút trên đường đi, ngược lại in ra -1.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~.

• Dòng thứ hai chứa ~N~ số nguyên cách nhau bởi khoảng trắng, số nguyên thứ i mô tả cho giá trị ~val[i]~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ mô tả tồn tại đường đi giữa hai đỉnh ~~u và ~v~

• ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn, tại dòng thứ i mô tả cho cặp Xi và ~K_i~.

Output

• Với mỗi truy vấn ~Q~ ghi ra trên một dòng là kết quả của truy vấn.

Ràng buộc

• ~1<=N<=10^5~

• ~1<=Q<=10~

• ~1<=val[i]<=10^9~

• ~1<=U,V,X<=N~

• ~1<=K<=10^{10}~

Ví dụ:

Input

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

Output

2
2

Sumo là một đứa trẻ rất thích đi du lịch qua những ngọn núi. Có ~N~ điểm trên các ngọn núi, mỗi điểm sẽ có một độ cao là ~H[i]~ được nối với nhau bởi M tuyến đường một chiều. Sumo nghĩ rằng một hành trình được cho là đặc biệt nhất nếu ~H[điểm kết thúc]~ – ~H[điểm xuất phát]~ có giá trị lớn nhất. Nhiệm vụ của bạn là giúp Sumo tìm ra giá trị ~H[điểm kết thúc]~ – ~H[điểm xuất phát]~ lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ testcase

Với mỗi testcase

• Dòng đầu tiên chứa 2 số ~N~ và ~M~

• Dòng thứ hai chứa ~N~ số nguyên, số nguyên thứ i biểu diễn cho ~H[i]~

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~.

Dữ liệu ra:

• Với mỗi test case ghi ra trên một dòng, một số nguyên duy nhất là giá trị chênh lệch chiều cao lớn nhất

Ràng buộc:

• ~1 \le T \le 10~

• ~0 \le H[i] \le 10^9~

• ~1 \le a_i,b_i ~ N~

SUBTASK

• Subtask 1: ~1 \le N \le 1000~; ~1 \le N \le 2000~

• Subtask 2: ~1 \le N \le 10^5~; ~1 \le N \le 2*10^5~.

Ví dụ:

Input:

1 
4 5 
2 4 10 7 
2 4 
1 2 
3 1 
3 4 
4 1 

Output:

5

Cho đồ thị vô hướng ~G~ có ~N~ đỉnh và ~M~ cạnh. Nhiệm vụ của bạn là xác định số cạnh tối đa trong bất kì thành phần liên thông nào của đồ thị. Giả sử như đồ thị có ~k~ thành phần liên thông với số cạnh trong mỗi thành phần liên thông là ~E_1, E_2, …, E_k~. kết quả là max(~E_1, E_2, …, E_k~)

Lưu ý: Đồ thị có thể chứa nhiều đường đi giữa hai đỉnh và khuyên. ~N~ đỉnh được đánh số từ 1 đến ~N~.

Dữ liệu vào:

• Dòng đầu tiên là 2 số nguyên ~N~ và ~M~

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên a và b mô tả tồn tại đường đi giữa hai đỉnh ~a~ và ~b~.

Dữ liệu ra:

• Ghi ra một số nguyên là kết quả của bài toán.

Ràng buộc:

• ~1 \le N \le 10^5~.

• ~1 \le M \le 10^5~.

• ~1 \le a,b \le N~.

Ví dụ:

Input

6 3 
1 2 
2 3 
4 5 

Output

2

GIẢI THÍCH

Đồ thị có 3 thành phần liên thông

• 1,2,3: có 2 cạnh

• 4,5: có 1 cạnh

• 6: có 0 cạnh

Thành phần liên thông có 2 cạnh là lớn nhất.