```go
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"strconv"
)

type Pair struct {
	x, y int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	var readInt = func() int {
		scanner.Scan()
		val, _ := strconv.Atoi(scanner.Text())
		return val
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	m := readInt()

	adj := make([][]bool, n)
	adj_mask := make([]uint32, n)
	for i := 0; i < n; i++ {
		adj[i] = make([]bool, n)
	}

	for i := 0; i < m; i++ {
		u := readInt()
		v := readInt()
		u--
		v--
		adj[u][v] = true
		adj[v][u] = true
		adj_mask[u] |= 1 << v
		adj_mask[v] |= 1 << u
	}

	dp_path := make([][14][14]bool, 1<<n)
	for i := 0; i < n; i++ {
		dp_path[1<<i][i][i] = true
	}

	for mask := 1; mask < (1<<n); mask++ {
		for i := 0; i < n; i++ {
			if (mask & (1 << i)) == 0 {
				continue
			}
			for j := 0; j < n; j++ {
				if (mask & (1 << j)) == 0 {
					continue
				}
				if dp_path[mask][i][j] {
					for k := 0; k < n; k++ {
						if (mask & (1 << k)) == 0 && adj[j][k] {
							dp_path[mask|(1<<k)][i][k] = true
							dp_path[mask|(1<<k)][k][i] = true
						}
					}
				}
			}
		}
	}

	valid_pairs := make([][]Pair, 1<<n)
	for mask := 1; mask < (1<<n); mask++ {
		if bits.OnesCount(uint(mask)) <= 1 {
			continue
		}
		for i := 0; i < n; i++ {
			if (mask & (1 << i)) == 0 {
				continue
			}
			for j := i + 1; j < n; j++ {
				if (mask & (1 << j)) != 0 && dp_path[mask][i][j] {
					valid_pairs[mask] = append(valid_pairs[mask], Pair{i, j})
				}
			}
		}
	}

	dp := make([]int, 1<<n)
	for i := range dp {
		dp[i] = 1e9
	}
	dp[1] = 0

	parent := make([]int, 1<<n)
	parent_T := make([]int, 1<<n)

	for mask := 1; mask < (1<<n); mask++ {
		if dp[mask] == 1e9 {
			continue
		}
		comp := ((1 << n) - 1) ^ mask
		for T := comp; T > 0; T = (T - 1) & comp {
			can_attach := false
			if bits.OnesCount(uint(T)) == 1 {
				x := bits.TrailingZeros(uint(T))
				if bits.OnesCount(uint(adj_mask[x]&uint32(mask))) >= 2 {
					can_attach = true
				}
			} else {
				for _, p := range valid_pairs[T] {
					if (adj_mask[p.x]&uint32(mask)) != 0 && (adj_mask[p.y]&uint32(mask)) != 0 {
						can_attach = true
						break
					}
				}
			}

			if can_attach {
				if dp[mask]+1 < dp[mask|T] {
					dp[mask|T] = dp[mask] + 1
					parent[mask|T] = mask
					parent_T[mask|T] = T
				}
			}
		}
	}

	curr := (1 << n) - 1
	var edges [][2]int

	for curr != 1 {
		p := parent[curr]
		T := parent_T[curr]

		if bits.OnesCount(uint(T)) == 1 {
			x := bits.TrailingZeros(uint(T))
			count := 0
			for u := 0; u < n; u++ {
				if (p & (1 << u)) != 0 && adj[x][u] {
					edges = append(edges, [2]int{x, u})
					count++
					if count == 2 {
						break
					}
				}
			}
		} else {
			var best_p Pair
			for _, pair := range valid_pairs[T] {
				if (adj_mask[pair.x]&uint32(p)) != 0 && (adj_mask[pair.y]&uint32(p)) != 0 {
					best_p = pair
					break
				}
			}

			for u := 0; u < n; u++ {
				if (p & (1 << u)) != 0 && adj[best_p.x][u] {
					edges = append(edges, [2]int{best_p.x, u})
					break
				}
			}

			for w := 0; w < n; w++ {
				if (p & (1 << w)) != 0 && adj[best_p.y][w] {
					edges = append(edges, [2]int{best_p.y, w})
					break
				}
			}

			curr_v := best_p.y
			curr_T := T
			for curr_v != best_p.x {
				curr_T ^= (1 << curr_v)
				for prev := 0; prev < n; prev++ {
					if (curr_T & (1 << prev)) != 0 && adj[curr_v][prev] && dp_path[curr_T][best_p.x][prev] {
						edges = append(edges, [2]int{curr_v, prev})
						curr_v = prev
						break
					}
				}
			}
		}
		curr = p
	}

	fmt.Println(len(edges))
	for _, edge := range edges {
		fmt.Printf("%d %d\n", edge[0]+1, edge[1]+1)
	}
}
```