1、哪里会有人喜欢孤独，不过是不喜欢失望罢了。

——《挪威的森林》

2、鱼说，你看不到我眼中的泪，因为我在水中。水说，我能感觉到你的泪，因为你在我心中。

——《鱼和水的爱恋》

3、白昼之光，岂知夜色之深。

——《且听风吟》

4、孤独一人也没关系，只要能发自内心地爱着一个人，人生就会有救。哪怕不能和他生活在一起。

——《1Q84》

5、我一直以为人是慢慢变老的，其实不是，人是一瞬间变老的。

——《舞！舞！舞！》

跳至内容
# 日期：2019年3月12日

## 村上春树选摘

## 【二分图最大匹配】Machine Schedule

## 【二分图最大匹配】Makers of Fine Wands since 382 BC

## 【二分图求最大独立集】Girls and Boys

## 【最大独立集】Graph Coloring

1、哪里会有人喜欢孤独，不过是不喜欢失望罢了。

——《挪威的森林》

2、鱼说，你看不到我眼中的泪，因为我在水中。水说，我能感觉到你的泪，因为你在我心中。

——《鱼和水的爱恋》

3、白昼之光，岂知夜色之深。

——《且听风吟》

4、孤独一人也没关系，只要能发自内心地爱着一个人，人生就会有救。哪怕不能和他生活在一起。

——《1Q84》

5、我一直以为人是慢慢变老的，其实不是，人是一瞬间变老的。

——《舞！舞！舞！》

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0.

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.

Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

InputThe input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.

OutputThe output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

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

Sample Output

3

In Diagon Alley ,there is only one Wand-seller,peeling gold letters over the door read Ollivanders: Makers of Fine Wands since 382 BC.A single wand lay on a faded purple cushion in the dusty window.

A tinkling bell rang somewhere in the depths of the shop as they stepped inside.It was a tiny place,empty execpt for a single spindly chair which Hagrid sat on to wait.Harry felt strangely as though he had entered a very strict library;he swallowd a log of new questions which had just occurred to him and looked instead at the thousands of narrow boxes piled neatly right up to the ceiling.For some reason,the back of his neck prickled.The very dust and silence in here seemed to tingle with some secret magic.

‘Good afternoon,’said a soft voice.Harry jumped.Hagrid must have jumped,too,because there was a loud crunching noise and he got quickly off the spindly chair.

An old man was standing before them, his wide pale eyes shining like moons through the gloom of the shop.

‘Hello,’ said Harry awkwardly.

‘Ah yes,’ said the man. ‘Yes,yes. I thought I’d be seeing you soon,Harry Potter.’It wasn’t a question.You have your mother’s eyes. It seems only yesterday she was in here herself,buying her first wand. Ten and a quarter inches long, swishy, made of willow. Nice wand for charm work.’

Mor Ollivander moved closer to Harry.Harry wished he would blink.Those sivery eyes were a bit creepy.

‘Your father, on the other hand, favoured a mahogany wand.Eleven inches.Pliable.A little more power and excellent for transfiguration.Well ,I say your father favoured it – it’s really the wand that choosed the wizard, of cource.’Yes, some wands fit some wizards ,as we all know.But what Harry doesn’t know is Ollivander have met a big trouble.That’s more than twenty years ago,When Harry’s father James Potter was still a student in Hogwarts.He went Diagon Alley to buy new books,passing by Ollivander’s shop.Ollivander was crazy for a problem:He was too busy to choose most suitable wand for every wizard.Even more,there are too many customer that day.Though Ollivader knew every wand’s favourite,he could not choose as many wizards as possible to get the wands. So James Potter,a very clever man ,gave him a magic disk with your program ,to help him sell wands as many as possible.

A tinkling bell rang somewhere in the depths of the shop as they stepped inside.It was a tiny place,empty execpt for a single spindly chair which Hagrid sat on to wait.Harry felt strangely as though he had entered a very strict library;he swallowd a log of new questions which had just occurred to him and looked instead at the thousands of narrow boxes piled neatly right up to the ceiling.For some reason,the back of his neck prickled.The very dust and silence in here seemed to tingle with some secret magic.

‘Good afternoon,’said a soft voice.Harry jumped.Hagrid must have jumped,too,because there was a loud crunching noise and he got quickly off the spindly chair.

An old man was standing before them, his wide pale eyes shining like moons through the gloom of the shop.

‘Hello,’ said Harry awkwardly.

‘Ah yes,’ said the man. ‘Yes,yes. I thought I’d be seeing you soon,Harry Potter.’It wasn’t a question.You have your mother’s eyes. It seems only yesterday she was in here herself,buying her first wand. Ten and a quarter inches long, swishy, made of willow. Nice wand for charm work.’

Mor Ollivander moved closer to Harry.Harry wished he would blink.Those sivery eyes were a bit creepy.

‘Your father, on the other hand, favoured a mahogany wand.Eleven inches.Pliable.A little more power and excellent for transfiguration.Well ,I say your father favoured it – it’s really the wand that choosed the wizard, of cource.’Yes, some wands fit some wizards ,as we all know.But what Harry doesn’t know is Ollivander have met a big trouble.That’s more than twenty years ago,When Harry’s father James Potter was still a student in Hogwarts.He went Diagon Alley to buy new books,passing by Ollivander’s shop.Ollivander was crazy for a problem:He was too busy to choose most suitable wand for every wizard.Even more,there are too many customer that day.Though Ollivader knew every wand’s favourite,he could not choose as many wizards as possible to get the wands. So James Potter,a very clever man ,gave him a magic disk with your program ,to help him sell wands as many as possible.

Please notice: one wand can only be sold to one wizard, and one wizard can only buy one wand,too.

InputThere are several cases. For each case, there is two integers N and M in the first line,which mean there is N wizards and M wands(0 < N <= M <= 100).

Then M lines contain the choices of each wand.The first integer in i+1th line is Ki,and after these there are Ki integers Bi,j which are the wizards who fit that wand. (0<=Ki<=N,1<=Bi,j<=N)

OutputOnly one integer,shows how many wands Ollivander can sell.

Sample Input

3 4 3 1 2 3 1 1 1 1 0

Sample Output

2 Wand 1 fits everyone, Wand 2,3 only fit the first wizard,and Wand 4 does not fit anyone.So Ollivanders can sell two wands: sell Wand 1 to Wizard 2 and Wand 2 to Wizard 1,or sell Wand 1 to Wizard 3 and Wand 3 to Wizard 1 ,or some other cases. But he cannot sell 3 wands because no 3 wands just fit 3 wizards.

Hint

Hint

the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.

The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:

the number of students

the description of each student, in the following format

student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 …

or

student_identifier:(0)

The student_identifier is an integer number between 0 and n-1, for n subjects.

For each given data set, the program should write to standard output a line containing the result.

Input

7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0

Output

5 2

Sample Input

7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0

Sample Output

5 2

You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.

Figure 1: An optimal graph with three black nodes

Input

The graph is given as a set of nodes denoted by numbers 1…n, n <= 100, and a set of undirected edges denoted by pairs of node numbers (n1, n2), n1 != n2. The input file contains m graphs. The number m is given on the first line. The first line of each graph contains n and k, the number of nodes and the number of edges, respectively. The following k lines contain the edges given by a pair of node numbers, which are separated by a space.

Output

The output should consists of 2m lines, two lines for each graph found in the input file. The first line of should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the list of black nodes, separated by a blank.

Sample Input

1 6 8 1 2 1 3 2 4 2 5 3 4 3 6 4 6 5 6

Sample Output

3 1 4 5