What's In A Name?

The FBI is conducting a surveillance of a known criminal hideout which serves as a communication center for a number of men and women of nefarious intent. Using sophisticated decryption software and good old fashion wiretaps, they are able to decode any e-mail messages leaving the site. However, before any arrest warrants can be served, they must match actual names with the user ID's on the messages. While these criminals are evil, they're not stupid, so they use random strings of letters for
their ID's (no dillingerj ID's found here). The FBI knows that each criminal uses only one ID. The only other information they have which will help them is a log of names of the people who enter and leave the hideout. In many cases, this is enough to link the names to the ID's.

Input

Input consists of one problem instance. The first line contains a single positive integer n indicating the number of criminals using the hideout. The maximum value for n will be 20. The next line contains the n user ID's, separated by single spaces. Next will be the log entries in chronological order. Each entry in the log has the form type arg , where type is either E, L or M: E indicates that criminal arg has entered the hideout; L indicates criminal arg has left the hideout; M indicates a message was intercepted from user ID arg. A line containing only the letter Q indicates the end of the log. Note that not all user ID's may be present in the log but each criminal name will be guaranteed to be in the log at least once. At the start of the log, the hideout is presumed to be empty. All names and user ID's consist of only lowercase letters and have length at most 20. Note: The line containing only the user ID's may contain more than 80 characters.

Output

Output consists of n lines, each containing a list of criminal names and their corresponding user ID's, if known. The list should be sorted in alphabetical order by the criminal names. Each line has the form name:userid , where name is the criminal's name and userid is either their user ID or the string ??? if their user ID could not be determined from the surveillance log.

Sample Input

7
bigman mangler sinbad fatman bigcheese frenchie capodicapo
E mugsy
E knuckles
M bigman
M mangler
L mugsy
E clyde
E bonnie
M bigman
M fatman
M frenchie
L clyde
M fatman
E ugati
M sinbad
E moriarty
E booth
Q

Sample Output

bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad

Source

East Central North America 2001

题目类型：反向构图+删边判断+二分图最大匹配

算法分析：首先这个图明显是一个二分图，这里构造二分图时使用了一个巧妙的方法：反向构造。即先在所有姓名-用户名对之间连边，然后每次在得到邮件信息(比如用户名a)时，将不在藏匿点的姓名和用户名a之间的边删去，最后就留下所有可能的情况。然后枚举每条边并将其删去，判断得到的最大匹配数是否小于没删去之前的最大匹配数。若小于，则说明当前边是一个唯一确定的边。否则当前边是目前还未确定的(注意只是目前还未确定的，有可能之后被唯一确定)

Asteroids

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.

Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input

* Line 1: Two integers N and K, separated by a single space.
* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

Output

* Line 1: The integer representing the minimum number of times Bessie must shoot.

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2

Hint

INPUT DETAILS:
The following diagram represents the data, where "X" is an asteroid and "." is empty space:
X.X
.X.
.X.

OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

Source

USACO 2005 November Gold

题目类型：最小点覆盖(二分图最大匹配)

算法分析：首先要对原图进行一个转化，将每行中的行星看做是在一个块中并标号，每列中的行星看做是在一个块中并标号，每个块中最多只需一个子弹就可以全部消灭行星。然后将横块和竖块中重合的块之间连线，这样原图就转化成一个等效的二分图。现在等效求解用多少点(块)来“覆盖”边，使得所有的边都被覆盖到。这样直接求解最大匹配即可

Air Raid

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

Input

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct.

Output

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.

Sample Input

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

Sample Output

2

1

Source

Dhaka 2002

题目类型：最小路径覆盖(二分图最大匹配)

算法分析：这是一道典型的最小路径覆盖问题，最小路径覆盖数等于顶点数减去最大匹配数。首先将每个点拆成两个点，然后在一边的点和另一边的点之间连一条边(有向边)。最后在这个二分图上跑一个最大匹配即可

Girls and Boys

In 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.

Input

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 (n <=500 ), for n subjects.

Output

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

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

Source

Southeastern Europe 2000

题目类型：最大点独立集(二分图最大匹配)

算法分析：这里给出n个点和m条边，求解最大的点独立集是多少，这里使用基于网络流的算法会比使用匈牙利算法要简单