Crowd

function dfs(v: int, g: int[][], d: int[], p: int[]) {
    for (let i = 0; i < g[v].length(); i += 1) {
        let u = g[v][i];
        if (d[u] != -1) { continue; }
        d[u] = d[v] + 1;
        p[u] = v;
        dfs(u, g, d, p);
    }
}

function solve(input: string) -> string {
    let z = input.split("\n");
    let n = int(z[0].split(" ")[0]);
    let m = int(z[0].split(" ")[1]);
    let k = int(z[0].split(" ")[2]);
    let g: int[][] = [];
    let d: int[] = [];
    let p: int[] = [];
    for (let i = 0; i < n; i += 1) {
        g.push([]);
        d.push(-1);
        p.push(-1);
    }
    for (let i = 0; i < m; i += 1) {
        let ps = z[i + 1].split(" ");
        let u = int(ps[0]) - 1;
        let v = int(ps[1]) - 1;
        g[u].push(v);
        g[v].push(u);
    }
    d[0] = 0;
    dfs(0, g, d, p);
    for (let i = 0; i < n; i += 1) {
        if (d[i] + 1 >= (n + k - 1) / k) {
            let res = "PATH\n" + string(d[i] + 1) + "\n";
            let ans: int[] = [];
            while (true) {
                ans.push(i + 1);
                if (i == 0) { return res + [from el in ans select string(el)].join(" "); }
                i = p[i];
            }
        }
    }
    let cyc: int[][] = [];
    let len: int[] = [];
    for (let v = 0; v < n && k > 0; v += 1) {
        let leaf = true;
        for (let i = 0; i < g[v].length(); i += 1) { leaf = leaf && (d[g[v][i]] < d[v]); }
        if (!leaf) { continue; }
        cyc.push([]);
        let x = -1;
        let y = -1;
        for (let i = 0; i < g[v].length(); i += 1) {
            let u = g[v][i];
            if (d[u] + 1 == d[v]) { continue; }
            if (x == -1) { x = u; }
            else if (y == -1) { y = u; }
            else { break; }
        }
        if (d[y] < d[x]) {
            let t = x;
            x = y;
            y = t;
        }
        if ((d[v] - d[x] + 1) % 3 != 0) {
            len.push(d[v] - d[x] + 1);
            let cur: int[] = [];
            let u = v;
            while (true) {
                cur.push(u + 1);
                if (u == x) { break; }
                u = p[v];
            }
            cyc.push(cur);
        }
        else if ((d[v] - d[y] + 1) % 3 != 0) {
            len.push(d[v] - d[y] + 1);
            let cur: int[] = [];
            let u = v;
            while (true) {
                cur.push(u + 1);
                if (u == y) { break; }
                u = p[v];
            }
            cyc.push(cur);
        }
        else {
            len.push(d[y] - d[x] + 2);
            let cur: int[] = [];
            let u = y;
            while (true) {
                cur.push(u + 1);
                if (u == x) { break; }
                u = p[v];
            }
            cur.push(v + 1);
            cyc.push(cur);
        }
        k -= 1;
    }
    let ans = "CYCLES\n";
    for (let i = 0; i < cyc.length(); i += 1) {
        ans += string(len[i]) + "\n" + [from el in cyc[i] select string(el)].join(" ") + "\n";
    }
    return ans;
}