Gigel is the owner of a castle with N rooms. The rooms are interconnected by a tree-like network of corridors (undirected graph without cycles). Each room has one parent room to which it is connected, as well as one or more children rooms to which it is also connected. Gigel wants to assign a security code M(i) to each room, and every path from the tree should satisfy the following property: if the security codes that are associated with each node (room) from the path are added together, than the sum of them must not divide to the length of the path (the length is equivalent with the number of nodes from the path). Multiple rooms can have the same security code. Data format Input The input file is called "maze.in". The first line contains a single integer N which represents the total number of rooms in the castle. Each of the next N1 lines contains two integers, which represent an edge from the graph (tree). Output The output file is called "maze.ouf". The first line contains N integers M(1),M(2),M(N) separated by space, which represent the security codes assigned to the nodes (rooms) from the tree. If multiple solutions exist, any one of them can be printed. Data limits 1