#P6453. Zju1364 Machine Schedule

Zju1364 Machine Schedule

Zju1364 Machine Schedule

题目描述

有两台机器 A 和 B。机器 A 有 nn 种工作模式,编号为 00 到 n−1n-1;机器 B 有 mm 种工作模式,编号为 00 到 m−1m-1。两台机器最初都处于模式 00。

有 kk 个任务。每个任务给出编号以及两个模式 x,yx,y,可以选择由处于模式 xx 的机器 A 完成,或由处于模式 yy 的机器 B 完成。

每当一台机器切换到另一种工作模式时,需要重启这台机器一次;另一台机器的模式不变。可以自行安排任务的执行顺序。求完成全部任务最少需要重启机器多少次。处于初始模式 00 时就能完成的任务,无需为此重启。

输入格式

从标准输入读入多组测试用例。

每组第一行三个正整数 n,m,kn,m,k,满足 n,m<100n,m<100,k<1000k<1000。

接下来 kk 行,每行三个整数 i,x,yi,x,y。其中 ii 是任务编号,xx 是机器 A 可用于完成该任务的模式,yy 是机器 B 可用于完成该任务的模式,满足 0≤x<n0\le x<n、0≤y<m0\le y<m。任务编号不决定执行顺序。

输入以单独一行 00 结束,结束标志不属于任何测试用例。

输出格式

每组输出一行一个整数,表示最少重启次数。

样例输入

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

样例说明

让机器 A 依次使用模式 1,21,2,共重启两次;机器 B 使用模式 33,重启一次。前八个任务可由机器 A 完成,最后两个任务可由机器 B 完成,总共重启三次。