Background

Special for beginners, ^_^

Description

有两个机器A，B。 A有n种工作模式0...n-1 B有m种工作模式0...m-1 然后又k个任务要做 每个任务可以用A机器的模式i或b机器的模式j来完成 机器开始都处于模式0 每次换模式时都要重启 问完成所有任务机器至少重启多少次

Format

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y. The input will be terminated by a line containing a single zero.

多组数据，以0结束，第一列输入没用

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Samples

5 5 10//N,M,K
0 1 1//第一个工作的描述
1 1 2//第二个工作的描述
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

3

Limitation

1s, 1024KiB for each test case.