Problem 2 - Maze (Java)

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 N-1 lines contains two integers, which represent an edge from the graph (tree).

Output

The output file is called maze.out.

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 <= M(i) <= 10^5

2 <= N <= 100

Example:

maze.in	maze.out
7 1 2 4 6 3 5 1 4 7 5 5 1	4 9 12 1 9 8 4

Explanation:

One example could be the path between 3 5 1 2 (the length of the path is 4 because there are 4 nodes in the path), where the sum of the security codes is 12 + 9 + 4 + 9 = 34, and 34 is not divisible by 4.