Machine Schedule

Machine scheduling is a classic problem in computer science that has been studied for a long time. Scheduling problems vary widely in the constraints that must be satisfied and in the kind of schedule desired. Here we consider a two-machine scheduling problem.

There are two machines, A and B. Machine A has n working modes, called mode 0, mode 1, ..., mode (n-1); machine B has m working modes, mode 0, mode 1, ..., mode (m-1). At the start, both machines are in mode 0.

You are given k jobs. Each job can be processed on exactly one of the two machines, in a specific mode. For job i the requirement is a triple (i, x, y): the job can be processed either on machine A in mode x, or on machine B in mode y.

To finish all the jobs you may have to change a machine's working mode from time to time, but a machine's mode can only be changed by restarting it manually. By reordering the jobs and choosing, for each job, which machine runs it, write a program that minimizes the number of machine restarts.

The input consists of several configurations. The first line of a configuration contains three positive integers n, m (n, m < 100) and k (k < 1000). Each of the next k lines describes one job as a triple i x y.

The input is terminated by a line containing a single 0.

For each configuration, print a single line containing one integer: the minimum number of machine restarts.