OI题库

想要“芝麻开门”，必须拥有一定数量的钱币，其中包括至少z枚金币，s枚银币和m枚铜币。 最初，阿里巴巴拥有三种钱币若干枚。他可以按照一定规则和芝麻之门的守护者进行交易。 每一种规则用以下形式表示：

z1, s1, m1 -> z2, s2, m2 (zi, si, mis属于集合{0,1,2,3,4})。

这样一种规则表示阿里巴巴可以将z1枚金币, s1枚银币, m1枚铜币换成z2枚金币, s2枚银币, m2枚铜币。 一次交易而得的钱币可以继续参加下一次的交易。

任务

从文件中读入几组数据；对于每一组数据：

• 阿里巴巴最初拥有的金银铜三种钱币数目
• “芝麻开门”所需的金银铜三种钱币数目
• 所有交易规则

对每一组数据，判断是否存在有限次的交易，使阿里巴巴能开启芝麻之门。如果是，则将最少交易次数输出，否则在输出NIE(波兰文NO)

把结果写进文件中

输入格式 文件的第一行有一个整数d<=10,表示数据的组数。

接下来是d组数据，每组占若干行。

第一行是三个数zp, sp, mp ，属于集合{0,1,2,3,4}。表示阿里巴巴最初拥有的金银铜数目。

第二行是三个数z, s, m ， 属于集合{0,1,2,3,4}。表示芝麻开门所需的金银铜数目。

第三行是规则总数r，1<=r<=10。

以下r行每行有六个数z1, s1, m1, z2, s2, m2 ，属于集合{0,1,2,3,4}。表示一种简单的交易z1, s1, m1 -> z2, s2, m2。

数字之间由若干个空格隔开。

输出格式

文件的第i行为第i组数据的答案：

一个非负整数——阿里巴巴要开启芝麻之门所需的最少交易次数，或者

单词NIE(波兰文NO)

样例输入

2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2

样例输出

NIE
9