AA国所在的星系共有nn个星球,星球间有mm条双向通道。AA国星球间的传送不仅耗时而且代价高昂。为了防止偷渡者的出现，AA国有一种特殊的手段可以检查每条通道是被通过了奇数次还是偶数次。
由于调兵，这mm条通道中的一些通道已经被经过了奇数次。现在你的任务是：安排尽量少的人，每个人在星球间沿一条路径传送(不一定是简单路径)，使得每条通道都被经过偶数次
输入包含多组数据，其中输入的第一行是数据组数TT。
第一行22个正整数n,mn,m，表示城市数和剩余的通道数目。
接下来mm行每行33个正整数a,b,ca,b,c，表示有一条城市aa和bb之间的双向通道。当c=1c=1时说明经过了奇数次，00表示经过了偶数次。
保证a≠ba≠b，且不存在i,ji,j，满足max(ai,bi)=max(aj,bj)max(ai,bi)=max(aj,bj)且min(ai,bi)=min(aj,bj)min(ai,bi)=min(aj,bj)。
第一行一个整数KK，表示你安排的人数。
接下来KK行，每行的第一个数为一个正整数ll，表示第ii个人走过的路径中的节点数。接下来ll个数表示第ii个人走过的路径是v1,v2,…,vlv1,v2,…,vl。
若对于一个测试点中的每组数据，你的程序第一行的答案都是正确的，且每组数据的输出都是满足格式要求的，那么设这个子任务的总分为xx，你可以得到0.35x0.35x的分数。注意为了得到这一部分的分数你没有必要输出正确的解，而是只要输出任意K条合法的路径即可。但你必须要保证对于一个测试点来说你输出的路径的ll之和不能超过5×1065×106且l>0l>0.
1 13 14 1 2 1 2 3 1 3 4 1 2 4 1 1 4 0 4 6 1 4 10 0 2 5 1 2 7 0 7 8 1 8 9 1 9 7 1 11 12 1 11 13 1
3 5 1 2 3 4 6 8 4 2 7 8 9 7 2 5 3 12 11 13
对于100%的数据，保证0≤ci≤1,∑n≤5×105,∑m≤5×1050≤ci≤1,∑n≤5×105,∑m≤5×105。