Divide Cities by Removing a Highway

You are given a tree representing a network of cities connected by highways. Your task is to determine the number of valid ways to build exactly one wall by removing a single highway such that the remaining cities are separated into two non-empty connected components.

Formally, consider a tree with n nodes and n-1 highways. Removing a highway will partition the tree into two connected subtrees. A partition is valid if both connected components contain at least one city. Use graph traversal techniques (such as breadth-first search) to determine if the removal of a highway results in a valid split.

All formulas should be represented in LaTeX format. For instance, the condition that both subtrees are non-empty can be written as \(\text{size}_1 > 0\) and \(\text{size}_2 > 0\). The answer is the number of highways (edges) that can be removed to satisfy this condition.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\), the number of cities.
• The second line contains an integer \(m\), the number of highways. It is guaranteed that the highways form a tree, hence \(m = n - 1\).
• Each of the next \(m\) lines contains two space-separated integers \(a\) and \(b\) indicating that there is a highway between city \(a\) and city \(b\).

outputFormat

The output is written to stdout and should be a single integer representing the number of ways to remove exactly one highway so that the cities are divided into two non-empty connected components.

4
3
1 2
2 3
3 4

3