def solv():
    N, K = map(int, input().split())
    graph = {}
    inverted_graph = {}

    for i in range(K):
        a, b = map(int, input().split())
        try:
            graph[a].add(b)
        except:
            graph[a] = {b}
        try:
            inverted_graph[b].add(a)
        except:
            inverted_graph[b] = {a}

    parents = []
    #   a --> b --> 2 <-- c
    #     \-> d
    for i in range(1, N + 1):
        if i not in graph:
            parents.append(i)
    # print(parents)
    result = [parents[:]]
    seen = set(parents)
    while graph:
        for i in parents:
            if i not in inverted_graph:
                continue
            for j in inverted_graph[i]:
                graph[j].remove(i)
                if len(graph[j]) == 0:
                    graph.pop(j)
        parents = []
        for i in range(1, N + 1):
            if i not in graph and i not in seen:
                parents.append(i)
                seen.add(i)
        result.append(parents[:])
    # print(result,graph)
    if len(seen) != N:
        print("0")
        return
    if len(result) == N:
        print("1")
        for i in result[::-1]:
            print(i[0], end=" ")
    else:
        # result=[ [1,2,3], [4,5]]
        print("2")
        for i in result[::-1]:
            print(*i, end=" ")
        print()
        for i in result[::-1]:
            print(*i[::-1], end=" ")




solv()