using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5 4");
WillReturn.Add("1 2");
WillReturn.Add("1 5");
WillReturn.Add("2 4");
WillReturn.Add("4 5");
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 0");
//3
}
else if (InputPattern == "Input3") {
WillReturn.Add("6 8");
WillReturn.Add("1 4");
WillReturn.Add("1 5");
WillReturn.Add("2 3");
WillReturn.Add("2 6");
WillReturn.Add("3 4");
WillReturn.Add("3 6");
WillReturn.Add("4 5");
WillReturn.Add("4 6");
//2
}
else if (InputPattern == "Input4") {
WillReturn.Add("8 21");
WillReturn.Add("1 4");
WillReturn.Add("5 7");
WillReturn.Add("8 4");
WillReturn.Add("3 4");
WillReturn.Add("2 5");
WillReturn.Add("8 1");
WillReturn.Add("5 1");
WillReturn.Add("2 8");
WillReturn.Add("2 1");
WillReturn.Add("2 4");
WillReturn.Add("3 1");
WillReturn.Add("6 7");
WillReturn.Add("5 8");
WillReturn.Add("2 7");
WillReturn.Add("6 8");
WillReturn.Add("5 4");
WillReturn.Add("3 8");
WillReturn.Add("7 3");
WillReturn.Add("7 8");
WillReturn.Add("5 3");
WillReturn.Add("7 4");
//13
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int UB;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int NodeCnt = wkArr[0];
UB = NodeCnt - 1;
int[,] FirstBanArr = new int[UB + 1, UB + 1];
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int FromNode = wkArr[0] - 1;
int ToNode = wkArr[1] - 1;
FirstBanArr[FromNode, ToNode]++;
FirstBanArr[ToNode, FromNode]++;
}
long BaseAnswer = 0;
// 自己ループの除去
for (int I = 0; I <= UB; I++) {
if (FirstBanArr[I, I] > 0) {
BaseAnswer += FirstBanArr[I, I];
FirstBanArr[I, I] = 0;
}
}
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnq;
WillEnq.BanArr = FirstBanArr;
WillEnq.CurrY = 0;
WillEnq.CurrX = 1;
WillEnq.Level = BaseAnswer;
Que.Enqueue(WillEnq);
var VisitedSet = new HashSet<decimal>();
long Answer = long.MaxValue;
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (IsClear(Dequeued.BanArr)) {
Answer = Math.Min(Answer, Dequeued.Level);
continue;
}
if (Answer <= Dequeued.Level) continue;
int CurrX = Dequeued.CurrX;
int CurrY = Dequeued.CurrY;
// 着目座標を変える遷移
int NewX = Dequeued.CurrX;
int NewY = Dequeued.CurrY;
NewX++;
bool IsOK = true;
if (NewX > UB) {
NewY++;
NewX = NewY + 1;
int EdgeCnt = GetEdgeCnt(Dequeued.BanArr, NewY - 1);
if (EdgeCnt != 2) {
IsOK = false;
}
}
if (IsOK && NewY <= UB && NewX <= UB) {
WillEnq.BanArr = Dequeued.BanArr;
WillEnq.CurrX = NewX;
WillEnq.CurrY = NewY;
WillEnq.Level = Dequeued.Level;
// 着目座標を変える遷移なので、コストによる枝切りはできない
Que.Enqueue(WillEnq);
}
// 辺を足す遷移
if (Dequeued.BanArr[CurrX, CurrY] == 0) {
WillEnq.BanArr = (int[,])Dequeued.BanArr.Clone();
WillEnq.BanArr[CurrX, CurrY]++;
WillEnq.BanArr[CurrY, CurrX]++;
WillEnq.CurrX = Dequeued.CurrX;
WillEnq.CurrY = Dequeued.CurrY;
WillEnq.Level = Dequeued.Level + 1;
decimal Hash = GetHash(WillEnq.BanArr);
if (VisitedSet.Add(Hash)) {
Que.Enqueue(WillEnq);
}
}
// 辺を消す遷移
if (Dequeued.BanArr[CurrX, CurrY] == 1) {
WillEnq.BanArr = (int[,])Dequeued.BanArr.Clone();
WillEnq.BanArr[CurrX, CurrY]--;
WillEnq.BanArr[CurrY, CurrX]--;
WillEnq.CurrX = Dequeued.CurrX;
WillEnq.CurrY = Dequeued.CurrY;
WillEnq.Level = Dequeued.Level + 1;
decimal Hash = GetHash(WillEnq.BanArr);
if (VisitedSet.Add(Hash)) {
Que.Enqueue(WillEnq);
}
}
}
Console.WriteLine(Answer);
}
// カレント行の枝の数を返す
static int GetEdgeCnt(int[,] pBanArr, int pY)
{
int Cnt = 0;
for (int I = 0; I <= UB; I++) {
Cnt += pBanArr[I, pY];
}
return Cnt;
}
// クリア判定
static bool IsClear(int[,] pBanArr)
{
for (int I = 0; I <= UB; I++) {
int Cnt = 0;
for (int J = 0; J <= UB; J++) {
Cnt += pBanArr[I, J];
}
if (Cnt != 2) {
return false;
}
}
return true;
}
struct JyoutaiDef
{
internal int[,] BanArr;
internal int CurrY;
internal int CurrX;
internal long Level;
}
static decimal GetHash(int[,] pBanArr)
{
decimal Hash = 0;
decimal Omomi = 1;
for (int I = 0; I <= UB; I++) {
for (int J = I + 1; J <= UB; J++) {
Hash += pBanArr[I, J] * Omomi;
Omomi *= 2;
}
}
return Hash;
}
////////////////////////////////////////////////////////////////
// 2次元配列(int型)のデバッグ出力
////////////////////////////////////////////////////////////////
static void PrintBan(int[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.Write(sb.ToString());
}
}