Statement

Given an undirected tree, count how many paths that have at least length of k.

Input

The first line is n (n <= 10 ^ 5) and k (k <= n) — the number of vertices and k as mentioned above.

Next n — 1 line represents an edge.

5 2

1 2

2 3

2 4

4 5

Output

6

Explain

All paths that have at least length of k:

(1,3): 1-2-3

(1,4): 1-2-4

(1,5): 1-2-4-5

(2,5): 2-4-5

(3,4): 3-2-4

(3,5): 3-2-4-5

Statement

Given n (n is even number and n <= 168) and a permutation of n. Our task is to do the least swap operator so that the value of

the permutation is maximum.

The value of a permutation is

Input

4

1 2 3 4

Output

3

Explain

1 2 3 4

Swap (p[1], p[3]) : 3 2 1 4

Swap (p[3], p[4]) : 3 2 4 1

Swap (p[2], p[4]) : 3 1 4 2

The value of the permutation now is abs(1 — 3) + abs(4 — 1) + abs(2 — 4) = 6

And we do 3 swap operators so the output is 3.

Statement

Given N (N <= 10^5) cats and M (M <= 10^5) dogs with their tag number (<= 10^9). A cat and a dog can be matched if they have the different tag number. Compute the greatest numbers of pairs that can be matched and print out the links.

Input

3 3 (N, M)

1 1 2 (tag number of N cats)

2 1 1 (tag number of M dogs)

Output

2

1 1

3 2

Explain

• The first cat(tag number: 1) matches with the first dog(tag number: 2)

• The third cat(tag number: 2) matches with the second dog(tag number: 1)

At first glance, I thought it was a simple maximum matching problem but then I realize that time complexity to build such bigraph is O(N * M). Are there other approaches to do it?