1678. The Exact Count, Or Too Many To Say

An undirected graph has n vertices and m edges, all of equal length. Print the EXACT number of shortest routes from vertex 1 to vertex n when that number is at most 10^18, and the words too many when it is larger. Print 0 if there is no route.

No modulus is allowed. Problem 1671 is the same question with the answer reduced modulo 1000000007, which hides exactly the thing this problem is about.

``` 4 vertices 1 - 2 2 - 4 1 - 3 3 - 4 -> 2

178 vertices, 59 diamonds in a chain -> 576460752303423488 181 vertices, 60 diamonds in a chain -> too many ```

## Why a modulus is normally used, which this problem exists to show

A chain of k diamonds, each a pair of equal-length sides, has 3k + 1 vertices and exactly 2^k shortest routes. At k = 59 that is 576460752303423488, which fits. At k = 60 it is 1152921504606846976, which is past 10^18 and must be reported as too many. The graph grew by three vertices and four edges.

So the count is not large because the input is large; it is exponential in the input. That is why every other counting problem reduces modulo something, and the price of the modulus is that the answer no longer tells you how many routes there are.

## The four things that have to be said

directed? no. Every edge may be walked either way. self-loops? allowed, and never on a shortest route. parallel edges? allowed, and TWO COPIES ARE TWO ROUTES. unreachable? yes, and the answer is then 0. When n is 1 the answer is 1.

## What most people try first

Problem 1671's accumulation with the modulus removed, in a 64 bit integer. The counts then wrap silently: a signed 64 bit integer holds 9223372036854775807, and 2^63 is just past that, so at k = 63 the answer becomes negative. The program prints a plausible-looking number, and nothing anywhere reports a problem.

Switching to a wide integer type, where the language has one, is correct and answers a different question: the exact count can have thousands of digits on a graph of two hundred vertices, and the statement asks for too many instead.

## A saturating addition

Carry the count as before, but make the addition CLAMP:

CAP = 10^18 add(a, b): s = a + b; return s if s <= CAP else CAP + 1

Then CAP + 1 is a sentinel meaning "more than the cap", and it propagates: any sum involving it also exceeds the cap, so once a vertex is over the limit everything downstream of it is too. At the end, print too many if the value exceeds CAP, and the value itself otherwise.

## Why the saturating addition cannot itself overflow

Both operands are at most CAP + 1, which is 10^18 + 1, so the sum a + b is at most about 2 * 10^18. A signed 64 bit integer holds 9223372036854775807, which is more than four times that, so the addition is computed exactly before it is clamped and the comparison against CAP is meaningful.

That ordering matters: clamp AFTER adding, never by testing a > CAP - b with the subtraction done in a narrower type. And the cap must be at most about a quarter of the type's limit for the argument to hold, which 10^18 is.

## Why the sentinel has to propagate rather than be checked once

A vertex whose count exceeds the cap may feed several others, and each of them exceeds it too. Treating "over the cap" as an ordinary large number and comparing only at the end would compare a wrapped value, which is the bug this replaces. Carrying CAP + 1 as a value that arithmetic preserves is what makes one check at the end sufficient.

## Cost

O(n + m), one breadth-first search, with O(n) memory. The graph is deliberately small, n at 2000 and m at 5000, because the difficulty here is the arithmetic rather than the search.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 5000` - `1 ≤ u, v ≤ n`