거센 강

샐리와 친구들이 거센 강의 한쪽 강둑에서 반대편 강둑까지 안전하게 건너려 합니다. 강에는 바위들이 흩어져 있습니다. 통나무 널빤지가 강둑과 일부 바위를, 그리고 일부 바위끼리를 잇습니다.

샐리가 가장 먼저 강을 건넙니다. 그녀는 왼쪽 강둑에서 출발해 널빤지를 한 번에 하나씩 건너며 오른쪽 강둑에 닿으려 합니다. 널빤지 하나를 건너는 데 1초가 걸립니다. 샐리가 널빤지를 건널 때마다 그 널빤지는 무너져 강에 빠지므로, 샐리도 친구들도 그 널빤지를 다시 쓸 수 없습니다. 샐리가 무사히 오른쪽 강둑에 닿으면 다른 친구가 건너려 하고, 이런 식으로 건널 수 있는 사람이 모두 건널 때까지 계속됩니다.

강둑, 바위, 널빤지의 그래프와 건너야 할 사람 수가 주어질 때, 모두가 안전하게 건너는 데 걸리는 최소 총 시간(초)을 구하세요. 모두가 건널 수 없다면, 왼쪽 강둑에 남아야 하는 사람 수의 최소값 $n$을 구하세요.

첫 줄에 정수 $P$, $R$, $L$이 주어집니다. $P$는 건너야 하는 사람 수, $R$은 강에 있는 바위 수, $L$은 바위와 강둑을 잇는 통나무 수입니다. 이 값들은 $1 \leq P \leq 10$, $0 \leq R \leq 1000$, $0 \leq L \leq 1000$을 만족합니다.

이어서 $L$개의 줄이 주어지며, 각 줄에는 통나무 한 개의 양 끝점 $E_1$과 $E_2$를 나타내는 정수 두 개가 들어 있습니다. 각 값은 $[-2, R-1]$ 범위에 있습니다. $-2$는 왼쪽 강둑, $-1$은 오른쪽 강둑이고, 그 밖의 값은 바위 번호입니다.

모든 통나무의 두 끝점은 서로 다르고, 같은 바위나 강둑 쌍을 잇는 통나무는 두 개 이상 없습니다. 오른쪽 강둑이나 일부 바위는 왼쪽 강둑에서 도달할 수 없을 수도 있습니다.

$P$명 모두 오른쪽 강둑에 닿을 수 있으면, 모두가 건너는 데 걸리는 최소 총 시간(초)을 정수 하나로 출력합니다.

그렇지 않으면 n people left behind를 출력합니다. 여기서 $n$은 왼쪽 강둑에 남아야 하는 사람 수의 최소값입니다.