package main

import (
	"fmt"
	"math/rand"
	"time"
)

type Graph struct {
	adjacencyList map[int][]int
}

func NewGraph() *Graph {
	return &Graph{adjacencyList: make(map[int][]int)}
}

func (g *Graph) addEdge(node1, node2 int) {
	g.adjacencyList[node1] = append(g.adjacencyList[node1], node2)
	g.adjacencyList[node2] = append(g.adjacencyList[node2], node1)
}

func generateConnectedGraph(n int) *Graph {
	rand.Seed(time.Now().UnixNano())
	graph := NewGraph()

	// Start with node 0
	for i := 1; i < n; i++ {
		// Connect the new node i to a random existing node
		existingNode := rand.Intn(i)
		graph.addEdge(i, existingNode)
	}

	return graph
}

func main() {
	graph := generateConnectedGraph(100)

	// Print the adjacency list to show the graph
	for node, edges := range graph.adjacencyList {
		fmt.Printf("Node %d: %v\n", node, edges)
	}
}