Problem M
On Average They're Purple

Alice and Bob are playing a game on a simple connected graph
with
Alice colors each edge in the graph red or blue.
A path is a sequence of edges where each pair of consecutive edges have a node in common. If the first edge in the pair is of a different color than the second edge, then that is a “color change.”
After Alice colors the graph, Bob chooses a path that begins
at node
Input
The first line contains two integer values
All edges in the graph are unique.
Output
Output the maximum number of color changes Alice can force
Bob to make on his route from node
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 3 1 2 2 3 |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
7 8 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 |
3 |