Raging River

Sally and her friends are trying to cross safely from one bank of a raging river to another. Boulders are scattered within the river. Log planks connect the banks to some of the boulders, and some pairs of boulders to each other.

Sally crosses the river first. She starts at the left bank and crosses one plank at a time, aiming to reach the right bank. Walking across a plank takes one second. Each time she crosses a plank, that plank collapses into the river, so neither Sally nor her friends can use it again. After Sally reaches the right bank safely, another friend tries to cross, and so on, until everyone who can make it has crossed.

Given the graph of banks, boulders, and planks, and the number of people who need to cross, find the smallest total time (in seconds) required for everyone to cross safely. If not everyone can cross, find the minimum number of people $n$ who must be left behind.

The first line contains three integers $P$, $R$, and $L$: the number of people $P$ who must cross, the number of boulders $R$ in the river, and the number of logs $L$ that span boulders and river banks. These satisfy $1 \leq P \leq 10$, $0 \leq R \leq 1000$, and $0 \leq L \leq 1000$.

Each of the next $L$ lines contains two integers $E_1$ and $E_2$, the endpoints of one log. Each value is in the range $[-2, R-1]$. The value $-2$ is the left river bank, $-1$ is the right river bank, and every other value is a boulder.

Every log has two distinct endpoints, and no two logs span the same pair of boulders or banks. The right bank or some boulders may not be reachable from the left bank.

If all $P$ people can reach the right bank, print one integer: the minimum total time (in seconds) for all of them to cross.

Otherwise, print n people left behind, where $n$ is the least number of people who must stay on the left bank.