#P4436. [Cerc2015]Kernel Knights

    ID: 3641 传统题 2000ms 512MiB 尝试: 69 已通过: 27 难度: 5 上传者: 标签>难度分类普及+/提高-图论功能图入度剥离独立集构造与建模奇偶性分析CF1800

[Cerc2015]Kernel Knights

[CERC 2015] Kernel Knights

题目描述

有两个家族参加骑士比武,各有 nn 名骑士。每名骑士恰好向另一家族的一名骑士发起挑战。挑战有方向,可以有多人挑战同一名骑士。

找出一个骑士集合 SS,使得:

  • SS 中没有骑士被 SS 中任何其他骑士挑战。
  • 每名不在 SS 中的骑士,都至少被一名 SS 中的骑士挑战。

保证至少存在一个符合条件的集合。

输入格式

第一行一个整数 nn(1≤n≤100 0001\le n\le100\,000)。两个家族的骑士编号分别为 1,…,n1,\ldots,n 和 n+1,…,2nn+1,\ldots,2n。

第二行 nn 个整数 f1,…,fnf_1,\ldots,f_n,其中 n+1≤fk≤2nn+1\le f_k\le2n,表示骑士 kk 挑战 fkf_k。

第三行 nn 个整数 s1,…,sns_1,\ldots,s_n,其中 1≤sk≤n1\le s_k\le n,表示骑士 n+kn+k 挑战 sks_k。

输出格式

在一行中输出集合 SS 中的所有骑士编号,用空格分隔,每个编号只输出一次。若有多个合法集合,输出任意一个。

样例 #1

样例输入 #1

4
5 6 7 7
1 3 2 3

样例输出 #1

1 2 4 8