题目描述

神话中的斯芬克斯向你提出了一道谜题。如果你不能正确回答，就会成为它下一顿饭。

这只斯芬克斯花了很长时间研究结构图论，因此这次的问题与图有关。

给定一个带正权的无向图。你需要把每个顶点染成黑色或白色，使得连接两个同色顶点的边的权值之和最小。

不过，斯芬克斯允许你使用一种特殊的逃生方式：如果图中存在一个长度至少为 $13$ 的简单环，那么你不必求上述最优染色，只需要输出这样一个环即可。

换句话说，你需要完成下列两件事中的任意一件：

1. 求出二染色时，同色端点边权和的最小可能值；
2. 找出图中一个长度至少为 $13$ 的简单环。

若图中存在这样的长环，输出长环和输出最优染色的目标值都将被接受。

输入格式

第一行包含两个整数 $n,m$：

• $1\le n\le 2000$；
• $0\le m\le 4000$。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,w_i$，表示顶点 $a_i$ 与 $b_i$ 之间有一条权值为 $w_i$ 的无向边，其中：

• $1\le a_i,b_i\le n$；
• $a_i\ne b_i$；
• $1\le w_i\le 10^9$。

任意两个顶点之间至多有一条边。

输出格式

你可以输出以下两种答案之一。

情况一：输出最优划分的目标值

第一行输出：

PODZIAL

第二行输出一个整数，表示把所有顶点染成黑、白两色后，所有两端颜色相同的边的权值之和的最小可能值。

情况二：输出一个长度至少为 13 的简单环

第一行输出：

CYKL

第二行输出整数 $k$，其中 $k\ge 13$，表示环的长度。

第三行输出 $k$ 个顶点编号，按它们在环上的顺序给出。顶点编号不要求按大小排序。

样例 1

4 4
1 2 4
2 3 5
3 1 6
1 4 10

一种正确输出为：

PODZIAL
4

样例 2

13 13
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 8 3
8 9 10
9 10 10
10 11 10
11 12 10
12 13 10
13 1 10

一种正确输出为：

PODZIAL
3

也可以输出：

CYKL
13
1 2 3 4 5 6 7 8 9 10 11 12 13

子任务