QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 32 MB Points totaux : 100

#11868. 两个政党

Statistiques

Byteasar 国王决定举办两场盛大的派对,并希望邀请 Byteotia 的每一位居民参加。当然,他希望每位居民都恰好被邀请参加其中一场派对。国王根据他丰富的经验得知,当一个人在派对中遇到的朋友数量为偶数时,他会玩得很开心。因此,他请求你将全国的居民分配到两场派对中,使得在各自派对中拥有偶数个朋友的人数尽可能多。允许出现一种平凡的分配方式,即其中一场派对没有邀请任何客人。相识关系是对称的,即如果 $A$ 认识 $B$,那么 $B$ 也认识 $A$。

编写一个程序:

  • 从标准输入读取 Byteotia 的居民人数及其相识关系描述,
  • 将居民分配到两场派对中,使得在各自派对中拥有偶数个朋友的人数尽可能多,
  • 将应该被邀请到第一场派对的人员名单写入标准输出。

输入格式

标准输入的第一行包含一个整数 $N$ ($1 \le N \le 200$),表示 Byteotia 的居民人数。居民编号从 $1$ 到 $N$。接下来的 $N$ 行描述了每个人的相识关系。第 $i+1$ 行的开头是一个整数 $l_i$ ($0 \le l_i \le N-1$),表示第 $i$ 位居民的朋友数量。随后是 $l_i$ 个互不相同的数字,表示第 $i$ 位居民的朋友编号。我们假设没有人是自己的朋友。这意味着每段相识关系会被记录两次:如果 $A$ 和 $B$ 互相认识,那么 $B$ 会出现在 $A$ 的朋友列表中,而 $A$ 也会出现在 $B$ 的朋友列表中。

输出格式

在标准输出的第一行,你的程序应写入一个整数 $M$,表示被邀请参加第一场派对的人数。在第二行,应写入这 $M$ 个人的编号。其余人将参加第二场派对。

本题存在多种正确的分配方案,你的程序只需输出其中任意一种即可。

样例

输入 1

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

输出 1

3
1 2 3

在上述示例中,每个人在各自的派对中都有偶数个朋友。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.