K-Star
A K-Star is a tree that contains a node v, so that when that node is taken to be the root, then for each its subtree T' stands that tree consisted of v and T' is a simple chain of length K (or in other words - a chain with K links). For a given graph, you have to find if the graph can represent a K-Star tree.
InputThe first line of the standard input contains two integers n (2 <= n <= 100 000) and K (1 <= K <= 10 000), where n represents the number of nodes in the given graph. The next n - 1 lines will contain two integers a and b (a != b, 1 <= a, b <= n), that represent that the two nodes a and b are connected in the graph. {a, b} is an edge.
OutputTo the first line of the standard input write 'Da', if the given graph can represent a K-Star, otherwise print 'Ne'.
Input:
Output:
4 1
1 2
1 3
1 4Output:
DaExplanation:
Node 1 is connected to all the other nodes, so taking node 1 as the root, each subtree is a path of length 1, actually simple chains are:
1-2; 1-3; 1-4..
Input:
Output:
13 3
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
1 11
11 12
12 13
Output:
DaExplanation:
Simple chains are:
1-2-3-4; 1-5-6-7; 1-8-9-10; 1-11-12-13.
Input:
Output:
6 2
1 2
2 3
1 4
1 5
1 6
Output:
NeInput:
Output:
5 1
1 2
1 3
2 3
5 4Output:
NeExplanation:
The given graph is not a tree.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.