← Home
package main

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

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c >= '0' && c <= '9' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.idx < fs.n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return val * sign
}

func bfs(start int, adj [][]int) (int, []int, []int) {
	n := len(adj) - 1
	dist := make([]int, n+1)
	parent := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = -1
	}
	q := make([]int, n)
	head, tail := 0, 0
	q[tail] = start
	tail++
	dist[start] = 0
	far := start

	for head < tail {
		v := q[head]
		head++
		if dist[v] > dist[far] {
			far = v
		}
		for _, to := range adj[v] {
			if dist[to] == -1 {
				dist[to] = dist[v] + 1
				parent[to] = v
				q[tail] = to
				tail++
			}
		}
	}
	return far, dist, parent
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	adj := make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		u := fs.NextInt()
		v := fs.NextInt()
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	s, _, _ := bfs(1, adj)
	t, dist, parent := bfs(s, adj)

	path := make([]int, 0)
	for v := t; ; v = parent[v] {
		path = append(path, v)
		if v == s {
			break
		}
	}

	dist2 := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dist2[i] = -1
	}
	q := make([]int, n)
	head, tail := 0, 0
	for _, v := range path {
		dist2[v] = 0
		q[tail] = v
		tail++
	}

	c := path[0]
	for head < tail {
		v := q[head]
		head++
		if dist2[v] > dist2[c] {
			c = v
		}
		for _, to := range adj[v] {
			if dist2[to] == -1 {
				dist2[to] = dist2[v] + 1
				q[tail] = to
				tail++
			}
		}
	}

	ans := dist[t] + dist2[c]
	if dist2[c] == 0 {
		for _, v := range path {
			if v != s && v != t {
				c = v
				break
			}
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprintln(out, ans)
	fmt.Fprintln(out, s, t, c)
	out.Flush()
}