The latest assignment in your graph theory course asks you to find the largest collection of edges in a graph which does not contain a cycle. However, you didn’t attend the class when the assignment was given so you’ve asked to see the notes of two of your friends. Unfortunately, one of your friends must have written down the wrong graph because their two graphs are different. In fact, the only thing the two graphs seem to have in common is that they both include the same number of edges m and the edges are numbered from 0 to m−1. Since you don’t know which graph is correct, you have two options. On one hand, you could flip a coin to guess which graph is correct. On the other hand, you could find the largest subset T of the integers from 0 to m − 1 so that in each of the two graphs, the edges which are numbered with an integer in T are acyclic. Hoping to guarantee some partial marks, you choose the second option. Input The first integer k denotes the number of test cases. Each test case begins with three integers n1, n2, m where n1 denotes the number of nodes in the first graph, n2 denotes the number of nodes in the second graph, and m denotes the number of edges in both graphs. Then m lines follow where the i-th such line consists of four numbers u1, v1, u2, v2 where 0 ≤ uj < vj < nj for each j = 1,2. This means (u1,v1) is an edge in the first graph and (u2,v2) is an edge in the second graph. No graph will have more than 50 nodes and the number of edges is at most 200. Furthermore, no graph will have two of the same edge. Output The output for each test case is a single line beginning with an integer t denoting the size of the largest subset T of integers 0 to m − 1 such that neither graph contains a cycle where all edges are numbered with an integer in T. Following this, you should output the numbers of the edges of such a subset in increasing order. Say these integers are e1 < e2 < . . . < et. If there are multiple subsets of integers of size t that contain no cycle in either graph, then output the one that minimizes et. If there are still multiple such subsets with the same minimum value for et, output the one among these that minimizes et−1, and so on. Sample Input 2 343 0101 1212 0223
2/2 555 0101 1202 1324 2334 2412 Sample Output 201 40234