QOJ.ac

QOJ

시간 제한: 10 s 메모리 제한: 1024 MB 총점: 100

#14858. 双人检测

통계

那是 1825 年 4 月 25 日。英国发明家 William Fothergill Cooke 和英国科学家 Charles Wheatstone 正在研究电报系统的早期原型。该系统由一个发送器和一个接收器组成。发送器可以向接收器发送消息,我们将其建模为一个正整数序列。然而,这个原型远非完美,因此经常会出现发送的整数实际上没有被接收到的情况。不过,整数在连接过程中绝不会被篡改,因此所有接收到的整数都保证是发送过的。

Cooke 和 Wheatstone 的电报机可以通过 5 根指针指向传输的字母来传输字母。CC BY-SA 4.0,由 Geni 上传至维基共享资源

为了弥补这一缺陷,Cooke 和 Wheatstone 提出了一种纠错码。他们共同商定了一个包含 $n$ 个可能消息的固定列表,并为每个消息分配了一个正整数列表。要发送列表中的某个消息,他们只需发送对应的整数列表。有时,某些整数可能会丢失或以不同的顺序到达,但如果保留了足够多的整数,他们希望仍然只有一种可能的消息。

你是一名邮递员,因此你将通信技术的创新视为对你工作保障的直接威胁。你决定干扰 Cooke 和 Wheatstone,以推迟他们电报系统的开发。你已经了解了他们的纠错码,并秘密获取了他们的消息列表以及所有整数列表的副本。你已经找到了一种强行中断某个整数传输的方法,因此你决定利用这一点来破坏他们的系统。为了避免引起怀疑,你决定在发送消息时,至少应保留两个整数不被中断。因此,你的目标是确定是否可以通过中断除其中两个整数之外的所有整数,来使任何消息变得具有歧义。这样,每当要发送这样的消息时,你就可以通过中断相应的整数来使其产生歧义。

注:有人可能会指出,Cooke 和 Wheatstone 实际上直到 1837 年才发布电报设计,但显然,这只意味着你成功解决了这个问题!:)

输入格式

输入包含以下内容:

  • 第一行包含一个整数 $n$ ($2 \le n \le 50\,000$),表示可能的消息数量。
  • 接下来 $n$ 行(每行对应一条消息),每行包含一个整数 $k$ ($2 \le k \le 10^5$),表示分配给该消息的整数个数,紧接着是这 $k$ 个整数 $x$ ($1 \le x \le 10^9$)。保证一条消息中的 $k$ 个整数两两不同。

所有消息中包含的整数总数最多为 $10^5$。

输出格式

如果存在一对不同的整数,它们被分配给了多个消息,请以任意顺序输出这两个整数,然后输出它们所分配到的其中两个消息的下标(从 1 开始编号)。否则,输出 impossible

如果存在多个有效解,你可以输出其中任意一个。

样例

输入样例 1

3
5 1 9 3 7 5
4 2 4 6 8
4 7 5 3 2

输出样例 1

3 5 3 1

输入样例 2

3
2 42 1337
2 42 123456789
2 1337 123456789

输出样例 2

impossible

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.