Minimum Hallway Reversal Cost

Problem Statement

The university's building layout consists of n classrooms and m one‐way hallways. Each hallway is represented as a directed edge from classroom \(a_i\) to classroom \(b_i\). Due to a design oversight, the current configuration might not form a proper tree structure — a directed acyclic graph (DAG) with exactly one source (a node with zero incoming hallways) that connects all the classrooms.

Your task is to determine the minimum number of hallways you need to reverse in order to obtain a valid configuration. That is, after reversing a set of hallways, the resulting graph should satisfy the following conditions:

• The graph is acyclic (contains no cycles).
• There is exactly one source (only one classroom has no incoming hallway), ensuring that the layout forms a rooted tree covering all classrooms.

If no such reversal leads to a valid proposal, output -1.

Input Constraints

The input consists of small integers so that a brute force solution exploring all reversal combinations is feasible.

Mathematical Formulation

Given a directed graph \(G = (V, E)\) where \(V = \{1, 2, \dots, n\}\) and \(E\) is a set of directed edges, find the minimum number of edges to reverse such that the modified graph \(G'\) satisfies:

[ \text{(i)}\quad G' \text{ is acyclic}, ] [ \text{(ii)}\quad |{ v \in V : \text{indegree}_{G'}(v) = 0 }| = 1. ]

If no valid \(G'\) exists after any combination of reversals, output -1.

inputFormat

Input Format

The input is provided via stdin and formatted as follows:

• The first line contains two integers n and m — the number of classrooms and hallways respectively.
• The next m lines each contain two integers a and b, representing a directed hallway from classroom a to classroom b.

Note: If m = 0, there may be no additional input lines.

outputFormat

Output Format

The output should be written to stdout and must consist of a single integer representing the minimum number of hallways that need to be reversed to form a valid proposal. If it is impossible to achieve a valid configuration, output -1.

## sample

3 2
1 2
2 3

0