Submission #1366794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366794		makon	Pragmatism (KAISTRUN26SPRING_F)	Pypy 3	100 / 100	237 ms	231504 KiB

Main

import sys
input = sys.stdin.readline

def main():
    n, m, k = map(int, input().split())

    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)

    need = n - 2 * k + 2

    state = [0] * (n + 1)
    idx = [0] * (n + 1)

    st = []
    done = []
    unvis = n
    p = 1

    def push(x):
        nonlocal unvis
        state[x] = 1
        st.append(x)
        unvis -= 1

    while True:
        if not st:
            while p <= n and state[p]:
                p += 1
            if p > n:
                break
            push(p)

        if len(st) >= need:
            print(1)
            print(*st[:need])
            return

        x = st[-1]

        while idx[x] < len(g[x]) and state[g[x][idx[x]]] != 0:
            idx[x] += 1

        if idx[x] < len(g[x]):
            y = g[x][idx[x]]
            idx[x] += 1
            push(y)
        else:
            if len(done) == k - 1 and unvis >= k:
                a = done[:] + [x]
                b = []

                for i in range(1, n + 1):
                    if state[i] == 0:
                        b.append(i)
                        if len(b) == k:
                            break

                print(2)
                print(*a)
                print(*b)
                return

            st.pop()
            state[x] = 2
            done.append(x)

if __name__ == "__main__": main()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 38%)

=======

• Subtask 1: 20 / 20
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40