Split into Two Paths

题目描述

给出一个有 n 个节点和 m 条边的有向无环图。\n确定是否可以在图中形成两条路径，使得图中的每个节点恰好出现在这两条路径中的一条中。注意路径中不需要包含图的所有边。

输入格式

第一行有两个整数 n 和 m：节点数和边数。节点编号为 1, 2, $\dots$, n。\n随后有 m 行描述边。每行有两个整数 a 和 b：图中存在一条从节点 a 到节点 b 的边。

输出格式

第一行输出 YES 如果可以构成这样的路径，否则输出 NO。\n如果可以构成路径，则在接下来的两行中输出它们。\n在两行的开头都输出路径中节点的数量，然后按顺序输出路径中的节点。相邻节点之间必须在图中有一条边。一条路径可以包含零个节点。\n如果存在多个解，可以输出任意一个解。

5 4
1 2
1 4
3 4
4 5

YES
2 1 2
3 3 4 5

提示

$2 \le n \le 2\cdot10^5$ $0 \le m \le 5\cdot 10^5$

标签: CSES3358|高级图论问题

来源

CSES3358|高级图论问题