链接: https://cses.fi/problemset/task/3358

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个含有 $n$ 个节点和 $m$ 条边的无环有向图。

判断能否在图中形成两条路径，使得图中的每个节点恰好出现在其中一条路径上。注意，图中的边不一定要全部出现在路径中。

输入

第一行包含两个整数 $n$ 和 $m$：节点数量和边的数量。节点编号为 $1,2,\dots,n$。

接下来有 $m$ 行描述边。每行包含两个整数 $a$ 和 $b$：表示图中有一条从节点 $a$ 指向节点 $b$ 的边。

输出

如果能形成这样的路径，先输出一行 YES，否则输出 NO。

如果可以形成，则在其后两行输出这两条路径。

在两行的开头，先输出该路径上的节点数量，然后按顺序排列路径上的节点。相邻节点之间在图中必须存在一条边。其中一条路径可以包含零个节点。

如果存在多组解，你可以输出任意一组。

数据范围

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

样例输入1

5 4
1 2
1 4
3 4
4 5

样例输出1

YES
2 1 2
3 3 4 5

样例输入2

5 4
1 2
1 3
1 4
1 5

样例输出2

NO