← 返回题目列表

AtCoder · typical90_bs

071. 模糊优先级(★7)

中文机器翻译题面 查看原题

配点: 7 点

問題文

(1,2,3, \cdots ,N) 的排列 给出了 P = (P_1,P_2,P_3, \cdots ,P_N) 满足以下条件: 请找到 K 件。 如果您没有 K ,请报告。 对于

  • i=1,2,3, \cdots ,M ,排列 在 P 中 找出满足 A_i 是 您也可以写 B_i 之前。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq K \leq 10
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq N
  • A_i \neq B_i
  • i \neq j 如果 (A_i,B_i) \neq (A_j,B_j)
  • 所有输入均为整数

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。

  1. (2 点): N \leq 10^3
  2. (3 点): K = 1
  3. (2分):没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N M K
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

满足条件的排列 P 是 在 K 如果没有 -1 输出。

如果存在,则输出为 由 K 行组成。每行包含满足条件的排列。 请按以下格式输出 P 。

P_1 P_2 P_3 \cdots P_N

K 排列必须不同。


入力例 1

5 2 3
1 2
3 4

出力例 1

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

此输入示例仅满足子任务 1 和 3 的约束。

順列 P 的条件是 在

  • 1 是 在 2 之前
  • 3 是 在 4 之前

可以得到第 2 个都满足这两个条件。

满足此条件的不同 K 个排列,如果输出的排列与示例不同也算正确。此外, K 个排列的输出顺序不同也算正确。


入力例 2

5 2 1
1 3
3 1

出力例 2

-1

此示例输入满足所有子任务约束。

满足条件的排列是 1 不存在。


入力例 3

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

出力例 3

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

此输入示例仅满足子任务 1 和 3 的约束。