2017-12-03 04:36
采纳率: 92.7%
浏览 823

Adopt or not

Problem Description
A two-party system is a form of party system where two major political parties dominate voting in nearly all elections, at every level. As a result, all, or nearly all, elected offices end up being held by candidates endorsed by one of the two major parties.Under a two-party system, one of the two parties typically holds a plurality in the legislature , and is referred to as the majority party. The smaller party is referred to as the minority party. Two-party systems are most common in polities with plurality vote counting system to prevent the problem of two similar candidates "splitting" the same voters.
There is a small country under a two-party system, the two parties are party A and party B. Every time when parliament convened, members of both parties will submit Their proposals. Some of the proposals will be raised by some members of the same party, but each person can submit only one. Of course, some people may object to certain proposals of the other party. If a member's proposal is adopted and all his objection cases are not adopted, then he will be pleased. As the country's president, you can arrange these proposals is adopted or not. You want to know , to make the numnber of people pleased with your decision maximum, which proposals must be adopted ?

On the first line one positive number: the number of testcases. After that per testcase:One line with three integers a, b, n (0<=a,b<=100 and 0<=n<=200): the number of proposals by party A, by party B, and number of members of the parliament. The proposals are numbered from 1 to a+b, the first a are party A's, the latter b are party B's.
n lines follow, each line represents a member of the parliament, begin with two integers ri,mi(1<=ri<=a+b, 0<=mi<a+b): the proposal submit by him, the number of proposals he object to. And then follows mi integers indicate the proposal he object to.

For each test case, you should output 2 lines. The first line will contains one integer, the maxium number of people pleased. The second line begins with an integer x, indicates there are x proposals must be adopted. Then output the x proposals in ascending order of their id. There is a space between each two proposals.

Sample Input
2 1 3
1 0
1 0
3 0
2 1 3
1 0
2 1 3
3 0
2 1 4
1 0
1 1 3
2 0
3 2 1 2

Sample Output
2 1 3
1 1
2 1 2

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新