2017. Best of a bad lot

Time limit: 1.0 second
Memory limit: 64 MB
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.
  1. Where were you at the moment of departure?
  2. Who did you see there?
The captain will make his decision based on contradictions in passengers’ testimonies. 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.

Input

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 nn2 … nm (0 ≤ m ≤ n − 1; 1 ≤ nj ≤ nnj ≠ inj < nj+1).

Output

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.

Samples

input output
3
bar 0
bar 1 1
pool 2 1 2
1
3
3
pool 2 2 3
pool 2 1 3
pool 2 1 2
1
1

Notes

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
 
 
 
 

最新文章

  1. Potocol Buffer详解
  2. 从扩展方法到匿名方法再到LINQ
  3. j-query j-query
  4. Javascript数组的indexOf()、lastIndexOf()方法
  5. 5.JSON
  6. js编码规范
  7. 一个很好的用C#导出数据到Excel模板的方法
  8. 推荐系统那点事 —— 基于Spark MLlib的特征选择
  9. 【Python3之正则re】
  10. PE解析器的编写(三)——区块表的解析
  11. Erlang调度器细节探析
  12. 【Alpha版本】冲刺阶段 - Day6 - 乘风
  13. 用Promise实现:带延时功能的链式调用
  14. selenium+python编写自动化脚本时,定位frame中对象操作
  15. .Net MVC发布出错 Server Error in &#39;/&#39; Application.
  16. ubuntu “下列的软件包有不能满足的依赖关系” 问题
  17. ASP.NET 预编译命令(解决发布后第一次访问慢问题)
  18. asp.net mvc中配置路由默认值(Area中)
  19. Yii2 数据库基本操作
  20. 在iOS 7中使用storyboard(part 1)

热门文章

  1. C++语言的I/o使用方法详解
  2. 分布式计算开源框架Hadoop入门实践(二)
  3. loadrunner之脚本篇——录制方式HTML-based和URL-based Script
  4. 优化MD5和IP在(MySQL)数据库中的存储
  5. android 7.0 (nougat)的编译优化-ninja
  6. Django---media静态文件的配置&amp;全局变量
  7. MySQL-LRU_List Free_List Flush_List
  8. myisam表修复
  9. nginx日志中$request_body 十六进制字符(\\x22) 引号问题处理记录
  10. 淘宝分类常见---部分显示和全部显示的js效果