410013 - 机器安排

现有两台机器A和B,A机器有0~n-1种工作模式,B机器有0~m-1种工作模式,初始时两台机器均在0工作模式。 现在有k项任务,任务可以以任意顺序被执行,每项任务都能在A机器或B机器的某个模式中完成,例如任务0可在A机器的模式3或B机器的模式4中完成,任务1可在A机器的模式2或B机器的模式4中完成,我们以(i,x,y)表示任务i可工作在A机器的x模式或B机器的y模式。 显然,要完成所有任务,我们需要时时变动机器的模式,请问如何才能使变动模式数最小?

Input

输入有多组测试数据,第一行包括三个整数n,m (n,m<100)和 k(k<1 000)。以下k行,每行三个参数即i,x,y。最末一行以0结束。

Output

一个整数,即最小变动数。

Examples

Input

5 5 10
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

Output

3
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题