Greed is all right, by the way I think greed is healthy. You can be greedy and still feel good about yourself. – Ivan F. Boesky Greedy coloring LOOSES Greedy coloring WINS Okay, don’t get confused. Greed is good and greed is bad — we all know that pretty well. There are problems that can be solved quite easily with greedy approach, and there are problems where it fails. Your mission, should you choose to accept it, is to show how bad a greedy approach can turn out to be. Given a number of colors, you’d have to show that a greedy approach can be as bad as to need all the colors given to color a tree. Some useful information: • Any tree with more than one node can be properly colored using two colors only. • Proper Coloring: A coloring of a graph is proper if no two adjacent vertices receive the same color. • Greedy approach for graph coloring: Given a permutation (ordering) of the vertices, color each vertex using the least available proper color. Example: Let A be a vertex that is connected to B, C and D. B is connected to C and D. Given the permutation CDBA, you’d assign color 1 to C, 1 to D, 2 to B and 3 to A. Thus the greedy approach needs 3 colors (which is also optimal in this case) to color this graph. • Degree of a Vertex: The number of vertices connected to this vertex.
2/2 Input There can be multiple test cases. For each test case you’d be given an integer K on a line. 1 < K < 16, the number of colors the greedy approach would at least need to color the tree. Output For each input case you are to print the tree, followed by an ordering of the vertices that the greedy approach would follow. In the first line, print the number of vertices N and the number of edges M in one line. In the next M lines, print M edges. An edge is represented by two integers separated by a space. In the last line for the test case, print an ordering of the vertices such that the greedy approach would need at least K colors to color the tree properly. The vertex numbers are to be separated by spaces. Any valid solution will be accepted. However, you must strictly adhere to the following constraints. Constraints: • Maximum degree for any vertex is K − 1 • There can be at most 2(K−1) vertices • Vertices are to be numbered 1...N Note: The image with the problem statement corresponds to the second sample output. A level order traversal on the tree would have allowed the greedy algorithm to use optimal coloring. Sample Input 2 4 Sample Output 21 12 12 87 12 23 25 43 16 81 67 84753621