Machine Schedule

Time limit1sMemory limit128 MB

Summary

Given jobs each runnable in one of two modes on two machines, minimize the number of mode changes needed to process all jobs.

Level: Medium7 of 10
Topics: Graph, Union-find, Greedy, Sorting
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1

Input

Expected output

Example 2
Input
```
2 2 1
0 1 1
0
```
Expected output
```
1
```
Example 3
Input
```
3 3 2
0 1 1
1 2 2
0
```
Expected output
```
2
```
Example 4
Input
```
5 5 4
0 0 0
1 0 3
2 4 0
3 0 1
0
```
Expected output
```
0
```