Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình. Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, nếu đó là một cây thì in ra "Yes", ngược lại in ra "No".

Input:

• Dòng đầu gồm 2 số ~n~ và ~m~. ~(2 \le n, m \le 1e5).~
• ~m~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u, v \le n)~ chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.

Output:

• Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".

Sample Test 1

Input:

3 2
1 2
2 3

Output:

Yes

Sample Test 2

Input:

3 3 
1 2 
2 3 
3 1

Output:

No

Cho một cây ~n~ đỉnh có đỉnh gốc là ~1~. Xác định độ sâu của mỗi đỉnh. Độ sâu của một đỉnh là số lượng cạnh trên đường đi từ đỉnh gốc đến nó.

Input

• Dòng đầu tiên gồm một số nguyên ~n~.
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u,v~, có một cạnh giữa ~u~ và ~v~.

Output

• In ra ~n~ số nguyên, số nguyên thứ ~i~ là độ sâu của cạnh ~i~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

5
1 2
1 3
3 4
3 5

Output:

0 1 1 2 2

Cho biết cấu trúc của một công ty, nhiệm vụ của bạn là tính số lượng cấp dưới của mỗi người.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^{5})~: số lượng nhân viên. Các nhân viên được đánh số ~1, 2, \ldots, n,~ và người có số ~1~ là tổng giám đốc của công ty.
• Sau đó là ~n - 1~ số nguyên: cấp trên trực tiếp trong công ty của mỗi nhân viên ~2, 3, \ldots, n~.

Output

• In ra ~n~ số nguyên: số lượng cấp dưới của mỗi người ~1, 2, \ldots, n~ .

Input

5
1 1 2 3

Output

4 1 1 0 0

Cho một cây vô hướng gồm ~n~ đỉnh, có gốc là đỉnh ~1~. Đỉnh ~i~ gồm một số ~a[i]~, nếu ~a[i] = 1~, nghĩa là có một chú mèo ở đỉnh ~i~, còn ngược lại thì không. Thinkies đang ở đỉnh ~1~, cậu chỉ có thể đi tới các đỉnh khác khi và chỉ khi từ đỉnh ~1~ tới đỉnh đó có số mèo trên các đỉnh liên tiếp nhỏ hơn hoặc bằng ~m~. Hãy đếm số đỉnh lá (các đỉnh không có đỉnh con) mà Thinkies có thể đi vào.

Input:

Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ (~1 \leq m \leq n \leq 10^5~).

Dòng sau gồm ~n~ số biểu thị dãy ~a~.

~n - 1~ dòng kế tiếp, mỗi dòng gồm 2 số ~u~ và ~v~, biểu thị có cạnh giữa 2 đỉnh ~u~ và ~v~.

Output:

In ra số lá mà Thinkies có thể đi vào

Mẫu:

Input:

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

Output:

2

Cho một cây có ~n~ đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n \le 10^5~.
• ~n - 1~ dòng tiếp theo chứa 2 số ~u, v (u, v \le n)~ là các cạnh của cây.

Output

• In ra một số nguyên số cạnh có thể xóa
• Nếu không thể có cách cắt thỏa mãn, in ra -1.

Sample Test 1

Input:

4
2 4
4 1
3 1

Output:

1

Sample Test 2

Input:

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

Output:

4

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 cây vô hướng không trọng số gồm ~n~ đỉnh.

Ban đầu, các cạnh được gán trọng số bằng ~0~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(a,b)~, tức là sẽ tăng các cạnh trên đường đi ngắn nhất từ đỉnh ~a~ tới đỉnh ~b~ lên ~1~ đơn vị.

Sau ~q~ truy vấn, hãy in ra giá trị của từng cạnh.

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.
• Dòng sau gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng là hai số nguyên dương ~(a,b)~ miêu tả truy vấn.

Constraint

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

Subtask

• Subtask ~1~ ~(40\%)~: ~n,q \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
2
1 3
2 4

Sample Output 1:

1
2
1

Cho một cây vô hướng ~n~ đỉnh. Trên mỗi đỉnh ~i~ sẽ có một trọng số nguyên ~a_i~. Định nghĩa ~g(u,v)~ là giá trị lớn nhất của trọng số các đỉnh trên đường đi ngắn nhất từ ~u~ đến ~v~. Hãy tính tổng ~g(u,v)~ với mọi cặp ~(1 \le u < v \le n)~.

Input:

• Dòng đầu là số nguyên dương ~n~. ~(2 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên ~a_i. (|a_i| <= 10^6)~.
• ~n-1~ dòng sau mỗi dòng gồm 2 số nguyên ~u,v~ miêu tả cạnh nối giữa 2 đỉnh ~u,v~.

Output:

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

Subtasks

• Subtask 1: ~n \leq 5000~.
• Subtask 2: Không có điều kiện gì thêm.

Sample Test

Input:

3
3 2 4
1 2
1 3

Output:

11

Giải thích:

Ta có : ~g(1,2) + g(1,3) + g(2,3) = 3 + 4 + 4 = 11.~

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3