using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.GetInt(); this.NodeCount = inpt[0]; int connecterCount = inpt[1]; int maxMove = inpt[2]; for (int i = 0; i < connecterCount; i++) { inpt = Reader.GetInt(); if (!roadDic.ContainsKey(inpt[0])) { roadDic.Add(inpt[0], new List()); } roadDic[inpt[0]].Add(inpt[1]); if (!roadDic.ContainsKey(inpt[1])) { roadDic.Add(inpt[1], new List()); } roadDic[inpt[1]].Add(inpt[0]); } ulong num = Convert.ToUInt64("1".PadLeft(61, '1'), 2); long ans = this.GetAns(1, maxMove, num); Console.WriteLine(ans); } private long GetAns(int nodeNum, int remain, ulong target) { ulong key = Convert.ToUInt64("1".PadRight(nodeNum, '0').PadLeft(61, '0'), 2); if (!dic.ContainsKey(nodeNum)) { dic.Add(nodeNum, new Dictionary>()); } if (!dic[nodeNum].ContainsKey(remain)) { dic[nodeNum].Add(remain, new Dictionary()); } if(dic[nodeNum][remain].ContainsKey(target)) { return dic[nodeNum][remain][target]; } long ans = 0; if (remain == 0) { if ((target & key) == key) { ans = (long)Math.Pow(2, nodeNum - 1) - 1; } } else { long addNum = 0; if((target & key) == key) { addNum = (long)Math.Pow(2, nodeNum - 1) - 1; } foreach (int num in roadDic[nodeNum]) { long ret = this.GetAns(num, remain - 1, target - key); if(ret >= 0) { ret += addNum; } ans = Math.Max(ans, ret); } } dic[nodeNum][remain].Add(target, ans); return ans; } private Dictionary> roadDic = new Dictionary>(); private Dictionary>> dic = new Dictionary>>(); private int NodeCount; public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 5 4 4 3 4 4 1 1 5 5 2 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } public static int[] GetInt(char delimiter = ' ', bool trim = false) { string inptStr = ReadLine(); if (trim) { inptStr = inptStr.Trim(); } string[] inpt = inptStr.Split(delimiter); int[] ret = new int[inpt.Length]; for (int i = 0; i < inpt.Length; i++) { ret[i] = int.Parse(inpt[i]); } return ret; } } static void Main() { Program prg = new Program(); prg.Proc(); } }