众所周知，机器调度是计算机科学中一个非常经典的问题，已经研究了很久。调度问题的约束条件和所需的调度类型有很大的差别。在这里，我们考虑一个2-机器调度问题。

有两台机器A和B。机器A有n种工作模式，称为mode0，mode1，…，moden−1；同样地，机器B有m种工作模式，mode0，mode1，…，modem−1。

开始时，它们都以模式0工作。

对于k个作业，每个作业都可以在两台机器的某个模式下进行处理。例如，作业0可以在机器A的模式3或机器B的模式4下处理，作业1可以在机器A的模式2或机器B的模式4下处理，等等。因此，对于第i个作业，可以将约束表示为一个三元组（i，x，y），表示作业i可以在机器A的模式x或机器B的模式y下进行处理。

显然，为了完成所有的作业，我们需要改变机器的工作模式。不幸的是，机器的工作模式只能通过手动重启来改变。

通过改变作业的顺序并将每个作业分配给合适的机器，请编写一个程序来最小化重启机器的次数。

第一个行包含三个正整数：n、m（n、m < 100）和k（k < 1000）。接下来的k行给出了k个作业的约束条件，每行三个整数：i，x，y。

输入将由一个包含单个零的行终止。

一个整数，表示重启机器的最小次数。