기계 스케줄

기계 스케줄링은 컴퓨터 과학의 고전적인 문제이다. 여기서는 두 대의 기계로 이루어진 스케줄링 문제를 다룬다.

기계 A와 기계 B가 있다. 기계 A는 mode 0, mode 1, ..., mode (n-1)의 n가지 작동 모드를 가지고, 기계 B는 mode 0, mode 1, ..., mode (m-1)의 m가지 작동 모드를 가진다. 처음에 두 기계는 모두 mode 0 상태이다.

k개의 작업이 주어진다. 각 작업은 두 기계 중 정확히 한 곳에서, 특정한 모드로 처리된다. 작업 i의 조건은 삼중항 (i, x, y)로 주어지며, 이 작업은 기계 A의 mode x에서 처리하거나 기계 B의 mode y에서 처리할 수 있다.

모든 작업을 수행하려면 기계의 모드를 때때로 바꿔야 하는데, 기계의 모드는 손으로 재시작해야만 변경할 수 있다. 작업의 순서를 바꾸고 각 작업을 어느 기계에서 처리할지 정해서, 기계를 재시작하는 횟수를 최소로 만드는 프로그램을 작성하라.

입력은 여러 개의 구성(configuration)으로 이루어진다. 한 구성의 첫 줄에는 세 양의 정수 n, m (n, m < 100)과 k (k < 1000)가 주어진다. 이어지는 k개의 줄에는 각 작업이 삼중항 i x y 형태로 주어진다.

입력은 0 하나만 있는 줄로 끝난다.

각 구성에 대해, 기계를 재시작하는 최소 횟수를 정수 하나로 한 줄에 출력한다.