#2622. 机器调度

机器调度

Description

有两台机器AABB

机器AAnn种工作模式,编号00nn-11

机器BBmm种工作模式,编号为00mm-11

它们一开始都在工作模式00下工作。

给定kk个作业,每个作业都可以在两台机器中的任何一台上以特定工作模式处理。

作业ii的约束表示为三元组((ii,xx,yy)),表示它可以在机器AA的工作模式xx下处理,或者在机器BB的工作模式yy下处理。

要完成所有工作,就需要不时地重启以修改机器的工作模式。

这里需要安排作业的顺序并分配适当的机器,使重启次数最少。

Format

Input

输入包含多个测试用例。

每个测试用例的第11行都包含三个正整数nnmmkknn,mm<<110000kk<<11000000

接下来的kk行是kk个作业的约束,每行都是一个三元组iixxyy

以输入单个“00”的行结束。

Output

对每个测试用例,都单行输出机器重启的最少次数。

Samples

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
3

来源

POJ1325