```go
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		x := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			x = x*10 + int(data[idx]-'0')
			idx++
		}
		return x
	}

	n := nextInt()
	m := nextInt()

	adj := make([][]int, n+1)
	for i := 0; i < m; i++ {
		u := nextInt()
		v := nextInt()
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	s := 1
	for s*s < n {
		s++
	}

	parent := make([]int, n+1)
	depth := make([]int, n+1)
	vis := make([]bool, n+1)
	it := make([]int, n+1)
	post := make([]int, 0, n)
	stack := make([]int, 0, n)

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	stack = append(stack, 1)
	vis[1] = true

	for len(stack) > 0 {
		v := stack[len(stack)-1]
		if it[v] < len(adj[v]) {
			to := adj[v][it[v]]
			it[v]++
			if to == parent[v] {
				continue
			}
			if !vis[to] {
				vis[to] = true
				parent[to] = v
				depth[to] = depth[v] + 1
				stack = append(stack, to)
			} else if depth[to] < depth[v] {
				if depth[v]-depth[to]+1 >= s {
					cycle := make([]int, 0, depth[v]-depth[to]+1)
					x := v
					for x != to {
						cycle = append(cycle, x)
						x = parent[x]
					}
					cycle = append(cycle, to)

					fmt.Fprintln(out, 2)
					fmt.Fprintln(out, len(cycle))
					for i, x := range cycle {
						if i > 0 {
							fmt.Fprint(out, " ")
						}
						fmt.Fprint(out, x)
					}
					fmt.Fprintln(out)
					return
				}
			}
		} else {
			post = append(post, v)
			stack = stack[:len(stack)-1]
		}
	}

	blocked := make([]bool, n+1)
	ans := make([]int, 0, s)
	for _, v := range post {
		if !blocked[v] {
			ans = append(ans, v)
			blocked[v] = true
			for _, to := range adj[v] {
				blocked[to] = true
			}
		}
	}

	fmt.Fprintln(out, 1)
	for i := 0; i < s; i++ {
		if i > 0 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, ans[i])
	}
	fmt.Fprintln(out)
}
```