A (free) tree T is a simple graph such that for every pair of vertices v and w there is a unique path from v to w.

A rooted tree is a tree where one of its vertices is designated the root.

Let T1 be a rooted tree with root r1 and let T2 be a rooted tree with root r2. 

The rooted trees T1 and T2 are isomorphic if there is a one-to-one, onto function f from the vertex set of T1 to the vertex set of T2 satisfying the following:

(a) (vi, vj) ∈ T1 if and only if (f(vi), f(vj)) ∈ T2.

(b) f(r1) = r2.

The level of a vertex v is the length of the simple path from the root to v.

The height of a rooted tree is the maximum level number of its vertices.

Let T be a tree with root v0. Suppose that x, y and z are vertices in T and that (v0, v1, ..., vn) is a simple path in T, then

(a) the parent of v(n) is v(n-1).

(c) a child of v(n-1) is vn.

(b) ancestors of v(n) are v0, ..., v(n-1).

(d) descendants of v(n-2) are v(n-1), vn.

(e) x and y are siblings if x and y are children of z.

(f) a terminal vertex (or a leaf) is a vertex that has no children.

(g) an internal (or branch) vertex is a vertex that has at least one child. 

(h) a subtree T' of a tree T is a graph where

V(T') = { v0 and the descendants of v0 }

E(T') = { e | e is an edge on a simple path from v0 to some vertex in V(T') }

Let T be a graph with n vertices. The following are equivalent.

(a) T is a tree.

(b) T is connected and acyclic.

(c) T is connected and has n-1 edges. //vertex들을 연결할 수 있는 최소한의 구조

(d) T is acyclic and has n-1 edges.

Graphs G1 and G2 are isomorphic if there is a one-to-one, onto function f from the vertices of G1 to vertices of G2 and a one-to-one, onto function g from the edges of G1 to the edges of G2, so that e=(v,w) in G1 if and only if g(e)=(f(v), f(w)) in G2.

Graphs G1 and G2 are isomorphic if and only if for some ordering of their vertices, their adjacency matrices are equal.

Graphs G1 and G2 are homeomorphic if G1 and G2 can be reduced to isomorphic graphs by performing a sequence of series reductions

A graph is planar if it can be drawn in the plane without its edges crossing,

if G is a connected planar graph, then v-e+f=2 and 2e>=sf.

G is a planar graph if and only if G does not contain a subgraph homeomorphic to either K5 or K3,3.

Input:    A connected, weighted graph in which all weights are positive;

vertices a and z

Output:    L(z), the length of a shortest path from a to z