QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#9276. 只是不同的规则...

Statistics

有若干张扑克牌。每张牌都有两面:黑色和白色,以及一个从 $1$ 到 $n$ 的点数。相同点数的牌可能有若干张。

你正在尝试解决一个谜题。在谜题中,所有牌被排列成 $m$ 条轨道。在一次操作中,你可以同时翻转所有特定点数的牌(即黑色变白色,白色变黑色)。如果每条轨道都至少包含一张白牌,你就赢了。

经过几个小时的苦思冥想,你终于解开了谜题……却发现你误解了规则:原本应该是每条轨道至少有一张白牌,而你现在所处的状态是每条轨道至多有一张白牌。你感到很失望,于是又进行了一系列无关紧要的翻转。

你能根据原始规则解决这个谜题吗?

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 200\,000$),分别表示点数和轨道的数量。接下来的 $m$ 行描述了各条轨道。

每条轨道的描述以整数 $k$ ($k \ge 1$) 开头,表示该轨道中牌的数量。随后是 $k$ 个绝对值不超过 $n$ 的非零整数,描述这些牌。正整数 $x$ 表示点数为 $x$ 的白牌,整数 $-x$ 表示点数为 $x$ 的黑牌。

所有轨道中牌的总数不超过 $500\,000$。

题目保证存在一种翻转序列,使得每条轨道至多包含一张白牌。但请注意,你的程序需要找到一种使得每条轨道至少包含一张白牌的状态(这并不总是可能的)。

输出格式

如果无法达到每条轨道至少有一张白牌的状态,输出 “No”。

否则,输出 “Yes” 以及一个整数 $f$ —— 所需翻转的次数。随后输出 $f$ 个介于 $1$ 到 $n$ 之间且互不相同的整数,表示要翻转的点数。

如果存在多种解,输出其中任意一种即可。

样例

样例输入 1

4 3
2 1 -2
2 -1 -3
3 1 3 4

样例输出 1

Yes
1
3

样例输入 2

1 2
1 1
1 -1

样例输出 2

No

说明

在第一个样例中,达到每条轨道至多有一张白牌的状态的方法之一是翻转点数为 $1$ 和 $4$ 的牌。如果你翻转点数为 $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.