Clear Cold Water

The hot, humid summers of Wisconsin's dairy country make the cows thirsty, so Farmer John pumps clear cold water from the barn out into a network of pipes to keep the herd cool. There are $N$ pipes ($3 \le N \le 99999$, with $N$ odd), numbered $1 \dots N$. As the water flows through the pipes the summer heat warms it, so Bessie wants to know how far every point in the network is from the barn in order to find the coldest water.

The pipes form a binary tree rooted at the barn. Every branch point has exactly two pipes leaving it, every pipe is exactly one unit long, and all $N$ pipes connect into this single tree.

Each pipe has an endpoint that is either a branch point or an open spigot, and that endpoint is identified by the pipe's own number. Pipe $1$ is attached to the barn, and the distance from its endpoint to the barn is $1$.

The map lists $C$ ($1 \le C \le N$) branch points. Each branch point is given as three integers: the endpoint $E_i$ ($1 \le E_i \le N$) of a pipe, and the two pipes $B1_i$ and $B2_i$ ($2 \le B1_i \le N$, $2 \le B2_i \le N$) that leave that endpoint. When a pipe branches, its distance carries on: the endpoints of $B1_i$ and $B2_i$ are one unit farther from the barn than the endpoint of $E_i$.

Using the map, report the distance from the barn to the endpoint of every pipe.

• Line 1: two space-separated integers, $N$ and $C$.
• Lines 2 to $C+1$: line $i+1$ describes one branch point with three space-separated integers $E_i$, $B1_i$, and $B2_i$. The endpoint of pipe $E_i$ is a branch point from which pipes $B1_i$ and $B2_i$ leave.

• Lines 1 to $N$: line $i$ contains a single integer, the distance from the barn to the endpoint of pipe $i$.

The first example describes this pipe map:

+------+
| Barn |
+------+
   | 1
   *
2 / \ 3
     *
  4 / \ 5

Pipe $1$ is always distance $1$ from the barn. Pipes $2$ and $3$ branch from the endpoint of pipe $1$, so they are distance $2$. Pipes $4$ and $5$ branch from the endpoint of pipe $3$, so they are distance $3$.