A cruise liner hasn’t moved away from the land even for three miles
when it became apparent that somebody has drowned one of the stewards
in the swimming pool. The captain promised to make an investigation
personally and to throw the villains overboard.
He is going to find the group of murderers by asking each of
n passengers two following questions.
- Where were you at the moment of departure?
- Who did you see there?
The captain will make his decision based on contradictions in passengers’
For example, if one passenger says that he was in his room,
and another passenger says that he saw the first one near the swimming pool,
then one of these two is for sure mixed up with murder.
However, if passenger A didn’t see some other passenger B at the place,
where passenger B really was,
the captain wouldn’t consider it a contradiction,
because passenger B could have just been unnoticed there.
The investigation is unlikely to be reliable, because the murderers have agreed
that their testimonies will have no contradictions between them.
As for the honest people, they have nothing to hide and will tell only the truth.
You volunteered to compare the mismatches in the passengers’ answers and
reveal a group of suspects. Moreover, you want to give out to the captain
the smallest possible group of passengers.
If somebody has to become the feeding stuff for sharks today,
let as few people as possible suffer.
The first line contains an integer n that is the number of the passengers
(2 ≤ n ≤ 400). Next n lines contain the testimonies of each
of the passengers. The i-th line starts with the place
where the i-th passenger said he was at the moment of departure
that is a non-empty string up to twenty lowercase Latin letters long.
The place is followed by the list of the passengers the i-th passenger saw there
in the form m n1 n2 … nm
(0 ≤ m ≤ n − 1; 1 ≤ nj ≤ n; nj ≠ i; nj < nj+1).
In the first line output a positive integer that is the number of
the passengers in the suspect group. In the second line output
the numbers of these suspects in any order. If the problem has several
solutions, output any of them. It is guaranteed that at least one solution exists.
bar 1 1
pool 2 1 2
pool 2 2 3
pool 2 1 3
pool 2 1 2
In the first example it is possible that both the first and the second
passengers are murderers, and the third one tells the truth.
But it is also possible that the first two tell the truth and the third one is a murderer.
It is needed to output the second possibility since the group of suspects in it is smaller.
In the second example all passengers do not have testimony contradictions,
so any of them could be a murderer.
Problem Author: Oleg Dolgorukov
Problem Source: NEERC 2014, Eastern subregional contest