luogu#P3104. [USACO14MAR] Counting Friends G

[USACO14MAR] Counting Friends G

题目描述

FJ 的 N(2N500)N(2 \le N \le 500) 头奶牛加入了社交网络“牛书”。

每一头奶牛在牛书上都有一个或多个朋友,于是 FJ 做了一个列表,列出了每头奶牛的朋友数量。但在这一过程中,他错误地将一个额外的数加入了列表(所以最终的列表包含 N+1N+1 个数,而不是预期的 NN 个数)。

请帮助 FJ 找出哪一个数可能是错误的那个数。

输入格式

11 行:一个整数 NN

22N+2N+2 行:共 N+1N+1 个数,每一行表示一头奶牛的朋友数量,也有可能是错误的那个数。

输出格式

11 行:一个整数 KK,表示有多少个数可能是错误的(若 K=0K=0,表示移出任意一个数都无法产生一个可行的朋友配对)。

22K+1K+1 行:每一行包括一个 FJ 列表的编号,对应的数可能是那个错误的数。也就是说,这个数字被移除可使得剩余的 NN 个数字成为一组合法的朋友关系。编号按从小到大顺序输出。

4 
1 
2 
2 
1 
3 

3 
1 
4 
5 

提示

样例解释

FJ 有四头奶牛。其中两头有一个朋友,两头有两个朋友,一头有三个朋友(当然,其中一个数字是错误的,不应出现在列表上)。

移除 FJ 列表上的第一个数字,余下的序列是 2,2,1,32,2,1,3,是合法的。如果我们把四头奶牛命名为 A,B,C,DA,B,C,D,就有 (A,B),(A,C),(A,D),(B,C)(A,B),(A,C),(A,D),(B,C) 的配对方式符合要求。同样的,移除列表中的第四、第五个数字,也可以形成合法的朋友关系,移除数字 22 则无法形成合法的朋友关系。容易发现,若移除了数字 22,剩余的数字为奇数,显然无法形成合法的朋友关系。