Submission #48418685

---

Source Code Expand

using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers;
using System.Buffers.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using 凾 = System.Runtime.CompilerServices.MethodImplAttribute;
#region Expanded by https://github.com/kzrnm/SourceExpander
//LICENSE:
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using M=MethodImplAttribute;using R=ConsoleReader;public class ConsoleReader{protected internal const int BufSize=1<<12;[EditorBrowsable(EditorBrowsableState.Never)]public Stream Input{get;}[EditorBrowsable(EditorBrowsableState.Never)]public Encoding Encoding{get;}internal readonly byte[]buf;internal int pos;internal int len;[M(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[M(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[M(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){Input=input;Encoding=encoding;buf=new byte[bufferSize];}[M(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[^1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=Input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[^1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=Input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[^1]=10;pos=0;}[M(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[M(256)]public T Read<T>(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();if(typeof(T)==typeof(char[]))return(T)(object)AsciiChars();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[M(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[M(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[M(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[M(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[M(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[M(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}interface IBlock{bool Ok(byte b);}[System.Diagnostics.CodeAnalysis.SuppressMessage("Style","IDE0079")][System.Diagnostics.CodeAnalysis.SuppressMessage("Style","IDE0251")]struct AC:IBlock{[M(256)]public bool Ok(byte b)=>' '<b;}[System.Diagnostics.CodeAnalysis.SuppressMessage("Style","IDE0079")][System.Diagnostics.CodeAnalysis.SuppressMessage("Style","IDE0251")]struct LB:IBlock{[M(256)]public bool Ok(byte b)=>b!='\n'&&b!='\r';}[M(256)](byte[],int)InnerBlock<T>()where T:struct,IBlock{var bk=new T();var sb=new byte[32];int c=0;byte b;do b=ReadByte();while(b<=' ');do{sb[c++]=b;if(c>=sb.Length)Array.Resize(ref sb,sb.Length<<1);b=ReadByte();}while(bk.Ok(b));return(sb,c);}[M(256)]public string String(){var(sb,c)=InnerBlock<AC>();return Encoding.GetString(sb,0,c);}[M(256)]public string Line(){var(sb,c)=InnerBlock<LB>();return Encoding.GetString(sb,0,c);}[M(256)]public char[]StringChars(){var(sb,c)=InnerBlock<AC>();return Encoding.GetChars(sb,0,c);}[M(256)]public char[]LineChars(){var(sb,c)=InnerBlock<LB>();return Encoding.GetChars(sb,0,c);}[M(256)]public string Ascii()=>new(AsciiChars());[M(256)]public char[]AsciiChars(){var sb=new char[32];int c=0;byte b;do b=ReadByte();while(b<=' ');do{sb[c++]=(char)b;if(c>=sb.Length)Array.Resize(ref sb,sb.Length<<1);b=ReadByte();}while(' '<b);Array.Resize(ref sb,c);return sb;}[M(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[M(256)]public int Int0()=>Int()-1;[M(256)]public uint UInt0()=>UInt()-1;[M(256)]public long Long0()=>Long()-1;[M(256)]public ulong ULong0()=>ULong()-1;[M(256)]public static implicit operator int(R cr)=>cr.Int();[M(256)]public static implicit operator uint(R cr)=>cr.UInt();[M(256)]public static implicit operator long(R cr)=>cr.Long();[M(256)]public static implicit operator ulong(R cr)=>cr.ULong();[M(256)]public static implicit operator double(R cr)=>cr.Double();[M(256)]public static implicit operator decimal(R cr)=>cr.Decimal();[M(256)]public static implicit operator string(R cr)=>cr.Ascii();[M(256)]public static implicit operator char[](R cr)=>cr.AsciiChars();[M(256)]public T[]Repeat<T>(int count){var a=new T[count];for(int i=0;i<a.Length;i++)a[i]=Read<T>();return a;}[M(256)]public void Repeat<T>(Span<T>dst){foreach(ref var b in dst)b=Read<T>();}}}
namespace Kzrnm.Competitive.IO{using M=MethodImplAttribute;public class RepeatReader<R>where R:ConsoleReader{internal readonly R cr;[EditorBrowsable(EditorBrowsableState.Never)]public R ConsoleReader=>cr;[EditorBrowsable(EditorBrowsableState.Never)]public int Count{get;}[M(256)]public RepeatReader(R cr,int count){this.cr=cr;Count=count;}[M(256)]public string[]Ascii()=>Read<string>();[M(256)]public int[]Int()=>Read<int>();[M(256)]public uint[]UInt()=>Read<uint>();[M(256)]public long[]Long()=>Read<long>();[M(256)]public ulong[]ULong()=>Read<ulong>();[M(256)]public double[]Double()=>Read<double>();[M(256)]public decimal[]Decimal()=>Read<decimal>();[M(256)]public string[]Line(){var a=new string[Count];for(var i=0;i<a.Length;i++)a[i]=cr.Line();return a;}[M(256)]public string[]String(){var a=new string[Count];for(var i=0;i<a.Length;i++)a[i]=cr.String();return a;}[M(256)]public char[][]AsciiChars(){var a=new char[Count][];for(var i=0;i<a.Length;i++)a[i]=cr.AsciiChars();return a;}[M(256)]public char[][]LineChars(){var a=new char[Count][];for(var i=0;i<a.Length;i++)a[i]=cr.LineChars();return a;}[M(256)]public char[][]StringChars(){var a=new char[Count][];for(var i=0;i<a.Length;i++)a[i]=cr.StringChars();return a;}[M(256)]public int[]Int0(){var a=new int[Count];for(var i=0;i<Count;i++)a[i]=cr.Int0();return a;}[M(256)]public uint[]UInt0(){var a=new uint[Count];for(var i=0;i<Count;i++)a[i]=cr.UInt0();return a;}[M(256)]public long[]Long0(){var a=new long[Count];for(var i=0;i<Count;i++)a[i]=cr.Long0();return a;}[M(256)]public ulong[]ULong0(){var a=new ulong[Count];for(var i=0;i<Count;i++)a[i]=cr.ULong0();return a;}[M(256)]public static implicit operator int[](RepeatReader<R>rr)=>rr.Int();[M(256)]public static implicit operator uint[](RepeatReader<R>rr)=>rr.UInt();[M(256)]public static implicit operator long[](RepeatReader<R>rr)=>rr.Long();[M(256)]public static implicit operator ulong[](RepeatReader<R>rr)=>rr.ULong();[M(256)]public static implicit operator double[](RepeatReader<R>rr)=>rr.Double();[M(256)]public static implicit operator decimal[](RepeatReader<R>rr)=>rr.Decimal();[M(256)]public static implicit operator string[](RepeatReader<R>rr)=>rr.Ascii();[M(256)]public static implicit operator char[][](RepeatReader<R>rr)=>rr.AsciiChars();public T[]Read<T>(){var a=new T[Count];for(int i=0;i<a.Length;i++)a[i]=cr.Read<T>();return a;}[M(256)]public T[]Select<T>(Func<R,T>factory){var a=new T[Count];for(var i=0;i<a.Length;i++)a[i]=factory(cr);return a;}[M(256)]public void Select<T>(Span<T>dst,Func<R,T>factory){foreach(ref var b in dst)b=factory(cr);}[M(256)]public T[]Select<T>(Func<R,int,T>factory){var a=new T[Count];Select(a,factory);return a;}[M(256)]public void Select<T>(Span<T>dst,Func<R,int,T>factory){for(var i=0;i<dst.Length;i++)dst[i]=factory(cr,i);}}public static class RepeatEx{[M(256)]public static RepeatReader<ConsoleReader>Repeat(this ConsoleReader cr,int count)=>new(cr,count);}}
namespace Kzrnm.Competitive.IO{public sealed class PropertyConsoleReader:ConsoleReader{public PropertyConsoleReader():base(){}public PropertyConsoleReader(Stream input,Encoding encoding):base(input,encoding){}public PropertyConsoleReader(Stream input,Encoding encoding,int bufferSize):base(input,encoding,bufferSize){}public new int Int=>Int();public new int Int0=>Int0();public new uint UInt=>UInt();public new uint UInt0=>UInt0();public new long Long=>Long();public new long Long0=>Long0();public new ulong ULong=>ULong();public new ulong ULong0=>ULong0();public new double Double=>Double();public new decimal Decimal=>Decimal();public new string String=>String();public new string Line=>Line();public new string Ascii=>Ascii();public new char[]StringChars=>StringChars();public new char[]LineChars=>LineChars();public new char[]AsciiChars=>AsciiChars();public new char Char=>Char();}}
namespace Kzrnm.Competitive.IO{public class PropertyRepeatReader:RepeatReader<PropertyConsoleReader>{public PropertyRepeatReader(PropertyConsoleReader cr,int count):base(cr,count){}public new int[]Int=>Int();public new uint[]UInt=>UInt();public new long[]Long=>Long();public new ulong[]ULong=>ULong();public new double[]Double=>Double();public new decimal[]Decimal=>Decimal();public new string[]Ascii=>Ascii();public new string[]Line=>Line();public new string[]String=>String();public new char[][]AsciiChars=>AsciiChars();public new char[][]LineChars=>LineChars();public new char[][]StringChars=>StringChars();public new int[]Int0=>Int0();public new uint[]UInt0=>UInt0();public new long[]Long0=>Long0();public new ulong[]ULong0=>ULong0();}public static class PRepeatEx{[凾(256)]public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new(cr,count);}}
namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using M=MethodImplAttribute;using W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new(false);internal const int BufSize=1<<12;[EditorBrowsable(EditorBrowsableState.Never)]public Stream Output{get;}internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){Output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new(Output,Utf8NoBom);}[M(256)]public void Flush(){Output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[M(256)]private Span<byte>EnsureBuf(int size){if(buf.Length-len<size){Flush();}return buf.AsSpan(len,size);}[M(256|512)]public W Write<T>(T v){void FormatFloat(double d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10(Math.Abs(d)),32)),out b,new StandardFormat('F',20));void FormatDec(decimal d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10((double)Math.Abs(d)),32)),out b,new StandardFormat('F',20));int bw;if(typeof(T)==typeof(int))TryFormat((int)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(long))TryFormat((long)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(uint))TryFormat((uint)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(ulong))TryFormat((ulong)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(short))TryFormat((short)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(ushort))TryFormat((ushort)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(byte))TryFormat((byte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(sbyte))TryFormat((sbyte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(float))FormatFloat((float)(object)v,out bw);else if(typeof(T)==typeof(double))FormatFloat((double)(object)v,out bw);else if(typeof(T)==typeof(decimal))FormatDec((decimal)(object)v,out bw);else if(typeof(T)==typeof(char)){var dst=EnsureBuf(6);var c=(char)(object)v;if(c<0x7f){dst[0]=(byte)c;bw=1;}else{Span<char>s=stackalloc char[1]{c};bw=Utf8NoBom.GetBytes(s,dst);}}else if(v is char[]charr)return Write(charr.AsSpan());else if(v is IUtf8ConsoleWriterFormatter){((IUtf8ConsoleWriterFormatter)v).Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[M(256|512)]public W Write(ReadOnlySpan<char>v){var mlen=Utf8NoBom.GetMaxByteCount(v.Length);if(mlen>buf.Length){Flush();buf=new byte[mlen*2];}else if(mlen>buf.Length-len){Flush();}var bw=Utf8NoBom.GetBytes(v,buf.AsSpan(len));len+=bw;return this;}[M(256)]public W WriteLine()=>Write('\n');[M(256)]public W WriteLine<T>(T v){Write(v);return Write('\n');}[M(256)]public W WriteLine(ReadOnlySpan<char>v){Write(v);return Write('\n');}[M(256)]public W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[M(256)]public W WriteLines<T>(T[]col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[M(256)]public W WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[M(256)]public W WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[M(256)][EditorBrowsable(EditorBrowsableState.Never)]public W WriteMany<T>(char sep,IEnumerable<T>col){if(col is T[]a)return WriteMany(sep,(ReadOnlySpan<T>)a);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[M(256)][EditorBrowsable(EditorBrowsableState.Never)]public W WriteMany<T>(char sep,ReadOnlySpan<T>col){if(col.Length>0){Write(col[0]);foreach(var c in col[1..]){Write(sep);Write(c);}}return WriteLine();}}public interface IUtf8ConsoleWriterFormatter{void Write(W cw);}}
namespace Kzrnm.Competitive{using O=ConsoleOutput;public static class ConsoleOutputExt{[凾(256)]public static O ToConsoleOutput<T>(this T f)where T:IUtf8ConsoleWriterFormatter{var cw=O.cw;f.Write(cw);return cw.WriteLine();}}public struct ConsoleOutput{public static Utf8ConsoleWriter cw;public static implicit operator O(int v)=>cw.WriteLine(v);public static implicit operator O(long v)=>cw.WriteLine(v);public static implicit operator O(uint v)=>cw.WriteLine(v);public static implicit operator O(ulong v)=>cw.WriteLine(v);public static implicit operator O(double v)=>cw.WriteLine(v);public static implicit operator O(decimal v)=>cw.WriteLine(v);public static implicit operator O(char v)=>cw.WriteLine(v);public static implicit operator O(ReadOnlySpan<char>v)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan<char>)(v?"Yes":"No"));public static implicit operator O(Utf8ConsoleWriter _)=>default;}}
internal partial class Program{public PropertyConsoleReader cr;public Utf8ConsoleWriter cw;public Program(PropertyConsoleReader r,Utf8ConsoleWriter w){cr=r;ConsoleOutput.cw=cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr:1;while( --Q>=0)Calc();cw.Flush();}}
namespace Kzrnm.Competitive{public static class __UpdateExtension{[凾(256)]public static bool UpdateMax<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)<0){r=val;return true;}return false;}[凾(256)]public static bool UpdateMax<T>(this ref T r,params T[]vals)where T:struct,IComparable<T> =>r.UpdateMax(vals.Max());[凾(256)]public static bool UpdateMin<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)>0){r=val;return true;}return false;}[凾(256)]public static bool UpdateMin<T>(this ref T r,params T[]vals)where T:struct,IComparable<T> =>r.UpdateMin(vals.Min());}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
partial class Program
{
    const bool __ManyTestCases = false;
#if !LOCAL_RUNNING
    static void Main() => new Program(new(), new()).Run();
    [凾(256)]
#endif
    private ConsoleOutput? Calc()
    {
        int N = cr;
        int M = cr;
        var AB = cr.Repeat(M).Select<(int A, int B)>(cr => (cr.Int0, cr.Int0));
        var edges = new int[1 << N];
        for (int i = 1; i < edges.Length; i <<= 1)
        {
            edges[i] = i;
        }
        edges[0] = (1 << N) - 1;
        foreach (var (a, b) in AB)
        {
            edges[1 << a] |= 1 << b;
            edges[1 << b] |= 1 << a;
        }
        for (int i = 1; i < edges.Length; i++)
        {
            var sub = i & (i - 1);
            var single = sub ^ i;
            edges[i] = edges[sub] & edges[single];
            if ((edges[i] & i) != i)
                edges[i] = 0;
        }

        var dp = new int[1 << N];
        dp.AsSpan(1).Fill(N);
        for (int i = 1; i < dp.Length; i++)
        {
            if (edges[i] != 0)
                dp[i] = 1;
            else
                for (int sub = i, other = 0; sub > other; sub = (sub - 1) & i, other = ~sub & i)
                {
                    dp[i].UpdateMin(dp[sub] + dp[other]);
                }
        }
        return dp[^1];
    }
}

Submission Info

Judge Result