Datealive:ShadowTactics
题号:NC203036
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    《影子战术:将军之刃》是一部策略性潜入游戏。在这部游戏中,玩家率领一支影子般的队伍潜入敌后,完成任务。精通手里剑的隼人和善于装扮为艺妓的爱子将参加这次秘密任务,敌人分为守卫和平民两种。两位刺客有着能将人置于死地的专长。众所周知,杀光所有敌人就能够不为人知地潜入敌后。但是,为了完成游戏的成就,Kurumi决定不轻易杀死遇到的平民,必要时只击晕他们。守卫则是必须处决的。特别地,关卡中有一些平民被冠以开发者的名字,为了完成另一项成就,这些特殊的平民必须杀死。

    每个敌人都能看到一部分守卫或者平民。游戏中的守卫有两种,第一种是单人站在原地守岗,第二种则是两人一组地在某地谈话。两名守卫能够看到彼此当且仅当他们在某地谈话。当守卫发现刺客的行踪时会喊来武士,难以招架,所以Kurumi不会冒这个险。当平民发现自刺客的行踪时则会惊慌失措,向所有自己能看到的和能看到自己的守卫呼救,暴露刺客位置。平民不会加入战斗。由于平民很少且分散,每个守卫最多只会被一个平民看见,且平民无法互相看见。因为平民普遍胆小而无害,所以未发现刺客时能被平民看到的那些守卫,永远不会被其他守卫所关注

    再过个单位时间就要到Kurumi和Shido的约会时间了,可是她很想完成这个关卡。奈何Kurumi的队伍里没有武士角色,每个角色在个单位时间内只能干掉一个敌人或者击晕一个平民,不考虑行走时间。得益于游戏的"影子模式",Kurumi可以让两个角色同时行动,但这需要2个单位时间。虽然Kurumi能够通过影子瞬移到Shido身边,但是Kurumi还是有些担心来不及赶上约会,便决定使用刻刻帝的能力回到过去提早开始游戏。刻刻帝会损耗灵力,所以Kurumi拜托你计算出她最少要让时间倒流几分钟,并给出潜入各地点的顺序(即击晕或者暗杀的顺序)。

输入描述:

第一行输入个字符串,每一个字符串代表一位开发者的名字(仅包含字母和数字)。字符串长度不大于

第二行两个整数表示关卡中有  个敌人,所有敌人能看到的人数之和为

接下来行,每行两个整数和一个字符串 ,表示某敌人在地点处,表示守卫,表示平民,代表该敌人的名字(仅包含字母和数字)。只有守卫和守卫可能在同一个地点,且最多两人。

接下来行,每行两个整数表示地点处的敌人能够看见地点处的敌人。保证游戏没有bug,即不存在无法杀死所有守卫的情况。

输出描述:

第一行一个整数,表示需要倒流的单位时间。

第二行输出潜入各地点的顺序,如有多个方案,则输出字典序最小的方案。地点编号用空格隔开。注意,如果隼人和爱子同时对付两个不同地点的敌人,在字典序方案中表现为两地点标号紧邻且从小到大排列。

示例1

输入

复制
Christopher Adolfo Fabricio Vanessa Gabriela Geoffrey Owen Kipp Stepan Alex Danielle Alberto Rodrigo Viviana Calliope Gwendolyn
3 2
0 1 Qwen
1 2 Witcher
1 3 Flash
1 2
1 3

输出

复制
0
2 3
示例2

输入

复制
Christopher Adolfo Fabricio Vanessa Gabriela Geoffrey Owen Kipp Stepan Alex Danielle Alberto Rodrigo Viviana Calliope Gwendolyn
3 2
0 1 Owen
1 2 Witcher
1 3 Flash
1 2
1 3

输出

复制
0
1 2 3
示例3

输入

复制
Christopher Adolfo Fabricio Vanessa Gabriela Geoffrey Owen Kipp Stepan Alex Danielle Alberto Rodrigo Viviana Calliope Gwendolyn
7 6
1 1 Gabriela
1 2 Kong
1 3 Paul
1 4 Kami
1 5 Rodrigo
1 6 Killer
1 6 Max
1 4
2 4
3 5
2 5
4 6
5 6

输出

复制
2
1 2 3 4 5 6