BOJ 30659 Hora do rush

문제 링크:

문제 내용

어느 회사에서 퇴근 시간이 되면 회사 주차장에서 시간당 $p$대의 자동차가 빠져나옵니다. 이 자동차들은 일방통행 도로를 통해 움직이는데, 시간 당 어떤 도로를 통해 지나갈 수 있는 자동차의 수는 그 도로의 폭과 같습니다. 회사 주차장은 1번 정점에 있고, 더 이상 갈 곳이 없는 곳들이 자동차들의 도착점입니다. 교통 체증을 일으키지 않도록 자동차들이 움직이는 방법이 존재하는지 판별하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 시간당 대수 $p$, 도로의 교차점의 수 $n$, 도로의 수 $m$이 주어집니다. ($1 \le p \le 1000$, $1 \le n \le 100$, $1 \le m \le n(n-1)$)

그 다음 $m$줄에는 각각 도로의 시작점 $u$, 끝점 $v$, 도로의 폭 $w$가 주어집니다. ($1 \le u, v \le n$, $1 \le w \le 10$) 임의의 서로 다른 두 정점의 쌍 $(A, B)$에 대해, $u = A, v = B$인 경우와 $u = B, v = A$인 경우가 최대 한 번씩 주어집니다.

입력 끝에는 0 0 0이 주어집니다.

출력

각 테스트 케이스에 대해, 교통 체증을 일으키지 않을 수 있다면 SEM GARGALOS, 그렇지 않다면 COM GARGALOS를 출력합니다.

문제 풀이