結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー kzrnmkzrnm
提出日時 2023-01-03 05:29:01
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 43,063 bytes
コンパイル時間 7,587 ms
コンパイル使用メモリ 165,776 KB
実行使用メモリ 232,140 KB
最終ジャッジ日時 2024-05-05 06:59:04
合計ジャッジ時間 15,894 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
28,800 KB
testcase_01 AC 55 ms
28,800 KB
testcase_02 AC 54 ms
29,276 KB
testcase_03 WA -
testcase_04 AC 54 ms
29,020 KB
testcase_05 AC 60 ms
29,056 KB
testcase_06 WA -
testcase_07 AC 56 ms
28,928 KB
testcase_08 WA -
testcase_09 AC 59 ms
30,464 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 130 ms
51,840 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 58 ms
29,056 KB
testcase_34 AC 123 ms
51,328 KB
testcase_35 AC 156 ms
61,440 KB
testcase_36 AC 175 ms
56,576 KB
testcase_37 AC 57 ms
28,928 KB
testcase_38 WA -
testcase_39 AC 160 ms
63,232 KB
testcase_40 AC 145 ms
232,140 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (82 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers;
using System.Buffers.Text;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using static Kzrnm.Competitive.Global;
using 凾 = System.Runtime.CompilerServices.MethodImplAttribute;
partial class Program
{
    const bool __ManyTestCases = false;
#if !LOCAL_RUNNING
    static void Main()=>new Program(new PropertyConsoleReader(),new Utf8ConsoleWriter()).Run();
    [凾(256)]
#endif
    private ConsoleOutput? Calc()
    {
        int N = cr;
        int M = cr;
        int Q = cr;
        var g = GraphBuilder.Create(N, cr, M, false).ToGraph();
        var es = g.RemoveCycle();

        var uf = new DSU(N);
        foreach (var (u, v) in es)
            uf.Merge(u, v);
        while (--Q >= 0)
        {
            cw.WriteLine(YesNo(uf.Same(cr.Int0, cr.Int0)));
        }
        return null;
    }
}

#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 AtCoder{public class DSU{internal readonly int _n;public readonly int[]_parentOrSize;public DSU(int n){_n=n;_parentOrSize=new int[n];_parentOrSize.AsSpan().Fill(-1);}[凾(256)]public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_parentOrSize[x]<-_parentOrSize[y])(x,y)=(y,x);_parentOrSize[x]+=_parentOrSize[y];_parentOrSize[y]=x;return x;}[凾(256)]public bool Same(int a,int b){return Leader(a)==Leader(b);}[凾(256)]public int Leader(int a){if(_parentOrSize[a]<0)return a;while(0<=_parentOrSize[_parentOrSize[a]]){(a,_parentOrSize[a])=(_parentOrSize[a],_parentOrSize[_parentOrSize[a]]);}return _parentOrSize[a];}[凾(256)]public int Size(int a){return-_parentOrSize[Leader(a)];}[凾(256)]public int[][]Groups(){int[]leaderBuf=new int[_n];int[]id=new int[_n];var resultList=new SimpleList<int[]>(_n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_parentOrSize[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}}
namespace AtCoder.Internal{public class CSR<TEdge>:IEnumerable<(int from,TEdge edge)>{public readonly int[]Start;public readonly TEdge[]EList;public CSR(int n,ICollection<(int from,TEdge e)>edges){Start=new int[n+1];EList=new TEdge[edges.Count];foreach(var(from,_)in edges){Start[from+1]++;}for(int i=1;i<=n;i++){Start[i]+=Start[i-1];}var counter=(int[])Start.Clone();foreach(var(from,e)in edges){EList[counter[from]++]=e;}}public Enumerator GetEnumerator()=>new Enumerator(this);IEnumerator<(int from,TEdge edge)>IEnumerable<(int from,TEdge edge)>.GetEnumerator()=>GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();public struct Enumerator:IEnumerator<(int from,TEdge edge)>{public Enumerator(CSR<TEdge>g){_g=g;index=-1;start=0;}private readonly CSR<TEdge>_g;private int index;private int start;public(int from,TEdge edge)Current=>(start,_g.EList[index]);object IEnumerator.Current=>Current;[凾(256)]public bool MoveNext(){if( ++index<_g.Start[start+1])return true;return MoveNextStart();}private bool MoveNextStart(){for( ++start;start+1<_g.Start.Length;++start)if(index<_g.Start[start+1])return true;return false;}public void Reset(){index=-1;start=0;}void IDisposable.Dispose(){}}}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}[凾(256)]public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);[凾(256)]public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[凾(256)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}[凾(256)]public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}[凾(256)]public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}[凾(256)]public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}[凾(256)]public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}[凾(256)]public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}[凾(256)]public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}[凾(256)]public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}[凾(256)]public void Clear()=>Count=0;[凾(256)]public bool Contains(T item)=>IndexOf(item)>=0;[凾(256)]public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);[凾(256)]public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);[凾(256)]public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}[凾(256)]public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[凾(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[凾(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-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[buf.Length-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[buf.Length-1]=10;pos=0;}[凾(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[凾(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();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[凾(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[凾(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[凾(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[凾(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[凾(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[凾(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[凾(256)]public string String(){var sb=new List<byte>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[凾(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[凾(256)]public string Line(){var sb=new List<byte>();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[凾(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[凾(256)]public int Int0()=>Int()-1;[凾(256)]public uint UInt0()=>UInt()-1;[凾(256)]public long Long0()=>Long()-1;[凾(256)]public ulong ULong0()=>ULong()-1;[凾(256)]public static implicit operator int(_R cr)=>cr.Int();[凾(256)]public static implicit operator uint(_R cr)=>cr.UInt();[凾(256)]public static implicit operator long(_R cr)=>cr.Long();[凾(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[凾(256)]public static implicit operator double(_R cr)=>cr.Double();[凾(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[凾(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();return arr;}}}
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 Ascii=>Ascii();public new string Line=>Line();public new char Char=>Char();}}
namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using _W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new UTF8Encoding(false);internal const int BufSize=1<<12;internal readonly Stream output;internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){this.output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new StreamWriter(output,Utf8NoBom);}[凾(256)]public void Flush(){output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[凾(256)]private Span<byte>EnsureBuf(int size){if(buf.Length-len<size){Flush();}return buf.AsSpan(len,size);}[凾(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<0x007f){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 f){f.Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[凾(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;}[凾(256)]public _W WriteLine()=>Write('\n');[凾(256)]public _W WriteLine<T>(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpan<char>v){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');Write(tuple.Item3);Write(' ');return WriteLine(tuple.Item4);}[凾(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++){if(i!=0)Write(' ');Write(tuple[i]);}return WriteLine();}[凾(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin<T>(params T[]col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteLines<T>(T[]col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan<T>)array);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[凾(256)]private _W WriteMany<T>(char sep,ReadOnlySpan<T>col){if(col.Length>0){Write(col[0]);foreach(var c in col.Slice(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.Int:1;while( --Q>=0)Calc();cw.Flush();}}
namespace Kzrnm.Competitive{public class SparseTable<TValue,TOp>where TOp:struct,ISparseTableOperator<TValue>{private static TOp op=default;private readonly TValue[][]st;public int Length{get;}public SparseTable(TValue[]array){Length=array.Length;st=new TValue[BitOperations.Log2((uint)Length)+1][];st[0]=(TValue[])array.Clone();for(int i=1;i<st.Length;i++){var stp=st[i-1];var sti=st[i]=new TValue[Length-(1<<i)+1];for(int j=0;j<sti.Length;j++)sti[j]=op.Operate(stp[j],stp[j+(1<<(i-1))]);}}[凾(256)]public TValue Slice(int l,int length)=>Prod(l,l+length);[凾(256)]public TValue Prod(int l,int r){var b=BitOperations.Log2((uint)(r-l));var stb=st[b];return op.Operate(stb[l],stb[r-(1<<b)]);}private struct DebugItem{public DebugItem(int l,int r,TValue value){if(r-l==1)key=$"[{l}]";else key=$"[{l}-{r})";this.value=value;}private readonly string key;private readonly TValue value;}private class DebugView{private readonly SparseTable<TValue,TOp>st;public DebugView(SparseTable<TValue,TOp>st){this.st=st;}public DebugItem[]Items{get{var items=new List<DebugItem>(st.st.Length*st.Length);for(int b=0;b<st.st.Length;b++){var len=1<<b;var stb=st.st[b];for(int i=0;i<stb.Length;i++)items.Add(new DebugItem(i,i+len,stb[i]));}return items.ToArray();}}}}}
namespace Kzrnm.Competitive{public interface ISparseTableOperator<T>{T Operate(T x,T y);}}
namespace Kzrnm.Competitive{public static class __ArrayExtension{[凾(256)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[凾(256)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[凾(256)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[凾(256)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[凾(256)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[凾(256)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default)=>ref GetOrDummy(arr.AsSpan(),index,dummy);[凾(256)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,index3,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}[凾(256)]public static int FindByBinarySearch<T,TCv>(this T[]arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this Span<T>arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this ReadOnlySpan<T>arr,TCv value)where TCv:IComparable<T>{int ix=arr.BinarySearch(value);if(ix<0)ix=~ix;return ix;}}}
namespace Kzrnm.Competitive{public static class __MemoryMarshalExtension{private class ArrayVal<T>{public T[]arr;}[凾(256)]public static Span<T>AsSpan<T>(this List<T>list,int start=0)=>Unsafe.As<ArrayVal<T>>(list).arr.AsSpan(start,list.Count-start);[凾(256)]public static Span<TTo>Cast<TFrom,TTo>(this Span<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ReadOnlySpan<TTo>Cast<TFrom,TTo>(this ReadOnlySpan<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ref T GetReference<T>(this Span<T>span)=>ref MemoryMarshal.GetReference(span);[凾(256)]public static ref T GetReference<T>(this ReadOnlySpan<T>span)=>ref MemoryMarshal.GetReference(span);}}
namespace Kzrnm.Competitive{public static class __CollectionTupleExtension_Stack{[凾(256)]public static bool TryPop<T1,T2>(this Stack<(T1,T2)>stack,out T1 item1,out T2 item2){var ok=stack.TryPop(out var tuple);(item1,item2)=tuple;return ok;}[凾(256)]public static bool TryPop<T1,T2,T3>(this Stack<(T1,T2,T3)>stack,out T1 item1,out T2 item2,out T3 item3){var ok=stack.TryPop(out var tuple);(item1,item2,item3)=tuple;return ok;}[凾(256)]public static bool TryPeek<T1,T2>(this Stack<(T1,T2)>stack,out T1 item1,out T2 item2){var ok=stack.TryPeek(out var tuple);(item1,item2)=tuple;return ok;}[凾(256)]public static bool TryPeek<T1,T2,T3>(this Stack<(T1,T2,T3)>stack,out T1 item1,out T2 item2,out T3 item3){var ok=stack.TryPeek(out var tuple);(item1,item2,item3)=tuple;return ok;}}}
namespace Kzrnm.Competitive{public static class Global{[凾(256)]public static string YesNo(bool b)=>b?"Yes":"No";[凾(256)]public static string TakahashiAoki(bool b)=>b?"Takahashi":"Aoki";[凾(256)]public static T[]NewArray<T>(int len0,T value)where T:struct=>new T[len0].Fill(value);[凾(256)]public static T[]NewArray<T>(int len0,Func<T>factory){var arr=new T[len0];for(int i=0;i<arr.Length;i++)arr[i]=factory();return arr;}[凾(256)]public static T[][]NewArray<T>(int len0,int len1,T value)where T:struct{var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,value);return arr;}[凾(256)]public static T[][]NewArray<T>(int len0,int len1,Func<T>factory){var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,factory);return arr;}[凾(256)]public static T[][][]NewArray<T>(int len0,int len1,int len2,T value)where T:struct{var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,value);return arr;}[凾(256)]public static T[][][]NewArray<T>(int len0,int len1,int len2,Func<T>factory){var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,factory);return arr;}[凾(256)]public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,T value)where T:struct{var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,value);return arr;}[凾(256)]public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,Func<T>factory){var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,factory);return arr;}}}
namespace Kzrnm.Competitive{public class GraphBuilder{internal readonly EdgeContainer<GraphEdge>edgeContainer;public GraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<GraphEdge>(size,isDirected);}public static GraphBuilder Create(int count,ConsoleReader cr,int edgeCount,bool isDirected){var gb=new GraphBuilder(count,isDirected);for(var i=0;i<edgeCount;i++)gb.Add(cr.Int0(),cr.Int0());return gb;}public static GraphBuilder<int>CreateWithEdgeIndex(int count,ConsoleReader cr,int edgeCount,bool isDirected){var gb=new GraphBuilder<int>(count,isDirected);for(var i=0;i<edgeCount;i++)gb.Add(cr.Int0(),cr.Int0(),i);return gb;}public static GraphBuilder CreateTree(int count,ConsoleReader cr){var gb=new GraphBuilder(count,false);for(var i=1;i<count;i++)gb.Add(cr.Int0(),cr.Int0());return gb;}[凾(256)]public void Add(int from,int to)=>edgeContainer.Add(from,new GraphEdge(to));public SimpleGraph<GraphNode,GraphEdge>ToGraph()=>GraphBuilderLogic.ToGraph<SimpleGraph<GraphNode,GraphEdge>,GraphNode,GraphEdge,TOp>(edgeContainer);public TreeGraph<TreeNode,GraphEdge>ToTree(int root=0)=>GraphBuilderLogic.ToTree<TreeGraph<TreeNode,GraphEdge>,TreeNode,GraphEdge,TOp>(edgeContainer,root);struct TOp:IGraphBuildOperator<SimpleGraph<GraphNode,GraphEdge>,GraphNode,GraphEdge>,ITreeBuildOperator<TreeGraph<TreeNode,GraphEdge>,TreeNode,GraphEdge>{[凾(256)]public SimpleGraph<GraphNode,GraphEdge>Graph(GraphNode[]nodes,CSR<GraphEdge>edges)=>new SimpleGraph<GraphNode,GraphEdge>(nodes,edges);[凾(256)]public GraphNode Node(int i,GraphEdge[]parents,GraphEdge[]children)=>new GraphNode(i,parents,children);[凾(256)]public TreeGraph<TreeNode,GraphEdge>Tree(TreeNode[]nodes,int root,HeavyLightDecomposition<TreeNode,GraphEdge>hl)=>new TreeGraph<TreeNode,GraphEdge>(nodes,root,hl);[凾(256)]public TreeNode TreeNode(int i,int size,TreeNode parent,GraphEdge edge,GraphEdge[]children)=>new TreeNode(i,size,edge.Reversed(parent.Index),parent.Depth+1,children);[凾(256)]public TreeNode TreeRootNode(int i,int size,GraphEdge[]children)=>new TreeNode(i,size,GraphEdge.None,0,children);}}public readonly struct GraphEdge:IGraphEdge,IReversable<GraphEdge>,IEquatable<GraphEdge>{public static GraphEdge None{get;}=new GraphEdge(-1);public GraphEdge(int to){To=to;}public int To{get;}[凾(256)]public static implicit operator int(GraphEdge e)=>e.To;public override string ToString()=>To.ToString();[凾(256)]public GraphEdge Reversed(int from)=>new GraphEdge(from);public override int GetHashCode()=>To;public override bool Equals(object obj)=>obj is GraphEdge edge&&Equals(edge);public bool Equals(GraphEdge other)=>To==other.To;public static bool operator==(GraphEdge left,GraphEdge right)=>left.Equals(right);public static bool operator!=(GraphEdge left,GraphEdge right)=>!left.Equals(right);}public class GraphNode:IGraphNode<GraphEdge>,IEquatable<GraphNode>{public GraphNode(int i,GraphEdge[]parents,GraphEdge[]children){Index=i;Parents=parents;Children=children;}public int Index{get;}public GraphEdge[]Parents{get;}public GraphEdge[]Children{get;}public bool IsDirected=>Parents!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is GraphNode d&&Equals(d);public bool Equals(GraphNode other)=>Index==other?.Index;public override int GetHashCode()=>Index;}public class TreeNode:ITreeNode<GraphEdge>,IEquatable<TreeNode>{public TreeNode(int i,int size,GraphEdge parent,int depth,GraphEdge[]children){Index=i;Parent=parent;Children=children;Depth=depth;Size=size;}public int Index{get;}public GraphEdge Parent{get;}public GraphEdge[]Children{get;}public int Depth{get;}public int Size{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is TreeNode node&&Equals(node);public bool Equals(TreeNode other)=>other!=null&&Index==other.Index;public override int GetHashCode()=>Index;}}
namespace Kzrnm.Competitive{public class GraphBuilder<T>{internal readonly EdgeContainer<GraphEdge<T>>edgeContainer;public GraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<GraphEdge<T>>(size,isDirected);}[凾(256)]public void Add(int from,int to,T data)=>edgeContainer.Add(from,new GraphEdge<T>(to,data));public SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>ToGraph()=>GraphBuilderLogic.ToGraph<SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>,GraphNode<GraphEdge<T>>,GraphEdge<T>,TOp>(edgeContainer);public TreeGraph<TreeNode<T>,GraphEdge<T>>ToTree(int root=0)=>GraphBuilderLogic.ToTree<TreeGraph<TreeNode<T>,GraphEdge<T>>,TreeNode<T>,GraphEdge<T>,TOp>(edgeContainer,root);struct TOp:IGraphBuildOperator<SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>,GraphNode<GraphEdge<T>>,GraphEdge<T>>,ITreeBuildOperator<TreeGraph<TreeNode<T>,GraphEdge<T>>,TreeNode<T>,GraphEdge<T>>{[凾(256)]public SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>Graph(GraphNode<GraphEdge<T>>[]nodes,CSR<GraphEdge<T>>edges)=>new SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>(nodes,edges);[凾(256)]public GraphNode<GraphEdge<T>>Node(int i,GraphEdge<T>[]parents,GraphEdge<T>[]children)=>new GraphNode<GraphEdge<T>>(i,parents,children);[凾(256)]public TreeGraph<TreeNode<T>,GraphEdge<T>>Tree(TreeNode<T>[]nodes,int root,HeavyLightDecomposition<TreeNode<T>,GraphEdge<T>>hl)=>new TreeGraph<TreeNode<T>,GraphEdge<T>>(nodes,root,hl);[凾(256)]public TreeNode<T>TreeNode(int i,int size,TreeNode<T>parent,GraphEdge<T>edge,GraphEdge<T>[]children)=>new TreeNode<T>(i,size,edge.Reversed(parent.Index),parent.Depth+1,children);[凾(256)]public TreeNode<T>TreeRootNode(int i,int size,GraphEdge<T>[]children)=>new TreeNode<T>(i,size,GraphEdge<T>.None,0,children);}}public readonly struct GraphEdge<T>:IGraphEdge,IGraphData<T>,IReversable<GraphEdge<T>>,IEquatable<GraphEdge<T>>{public static GraphEdge<T>None{get;}=new GraphEdge<T>(-1,default);public GraphEdge(int to,T data){To=to;Data=data;}public T Data{get;}public int To{get;}[凾(256)]public static implicit operator int(GraphEdge<T>e)=>e.To;public override string ToString()=>$"to:{To}, Data:{Data}";[凾(256)]public void Deconstruct(out int to,out T data){to=To;data=Data;}[凾(256)]public GraphEdge<T>Reversed(int from)=>new GraphEdge<T>(from,Data);public override int GetHashCode()=>To;public override bool Equals(object obj)=>obj is GraphEdge<T>edge&&Equals(edge);public bool Equals(GraphEdge<T>other)=>To==other.To;public static bool operator==(GraphEdge<T>left,GraphEdge<T>right)=>left.Equals(right);public static bool operator!=(GraphEdge<T>left,GraphEdge<T>right)=>!left.Equals(right);}public class GraphNode<TEdge>:IGraphNode<TEdge>,IEquatable<GraphNode<TEdge>>where TEdge:IGraphEdge{public GraphNode(int i,TEdge[]parents,TEdge[]children){Index=i;Parents=parents;Children=children;}public int Index{get;}public TEdge[]Parents{get;}public TEdge[]Children{get;}public bool IsDirected=>Parents!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is GraphNode<TEdge>d&&Equals(d);public bool Equals(GraphNode<TEdge>other)=>Index==other?.Index;public override int GetHashCode()=>Index;}public class TreeNode<T>:ITreeNode<GraphEdge<T>>,IEquatable<TreeNode<T>>{public TreeNode(int i,int size,GraphEdge<T>parent,int depth,GraphEdge<T>[]children){Index=i;Parent=parent;Children=children;Depth=depth;Size=size;}public int Index{get;}public GraphEdge<T>Parent{get;}public GraphEdge<T>[]Children{get;}public int Depth{get;}public int Size{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is TreeNode<T>node&&Equals(node);public bool Equals(TreeNode<T>other)=>other!=null&&Index==other.Index;public override int GetHashCode()=>Index;}}
namespace Kzrnm.Competitive{public class SimpleGraph<TNode,TEdge>:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}[凾(256)]public TNode[]AsArray()=>Nodes;public TNode this[int index]{[凾(256)]get=>Nodes[index];}public int Length=>Nodes.Length;public SimpleGraph(TNode[]array,CSR<TEdge>edges){Nodes=array;Edges=edges;}}public class TreeGraph<TNode,TEdge>:ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{internal TNode[]Nodes{get;}[凾(256)]public TNode[]AsArray()=>Nodes;public TNode this[int index]{[凾(256)]get=>Nodes[index];}public int Length=>Nodes.Length;public int Root{get;}public HeavyLightDecomposition<TNode,TEdge>HlDecomposition{get;}public TreeGraph(TNode[]array,int root,HeavyLightDecomposition<TNode,TEdge>hl){Root=root;Nodes=array;HlDecomposition=hl;}}}
namespace Kzrnm.Competitive{public interface IReversable<T>where T:IGraphEdge{T Reversed(int from);}public interface IGraphEdge{int To{get;}}public interface IWGraphEdge<T>:IGraphEdge{T Value{get;}}public interface IGraphData<T>:IGraphEdge{T Data{get;}}public interface IGraphNode<out TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge[]Parents{get;}TEdge[]Children{get;}bool IsDirected{get;}}public interface ITreeNode<TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge Parent{get;}TEdge[]Children{get;}int Depth{get;}int Size{get;}}public interface IGraphBuildOperator<TGraph,TNode,TEdge>{TNode Node(int i,TEdge[]parents,TEdge[]children);TGraph Graph(TNode[]nodes,CSR<TEdge>edges);}public interface ITreeBuildOperator<TTree,TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{TNode TreeNode(int i,int size,TNode parent,TEdge parentEdge,TEdge[]children);TNode TreeRootNode(int i,int size,TEdge[]children);TTree Tree(TNode[]nodes,int root,HeavyLightDecomposition<TNode,TEdge>hl);}public interface IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{CSR<TEdge>Edges{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public interface ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{int Root{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}HeavyLightDecomposition<TNode,TEdge>HlDecomposition{get;}}public class EdgeContainer<TEdge>where TEdge:IGraphEdge{public int Length{get;}public bool IsDirected{get;}public readonly List<(int from,TEdge edge)>edges;public readonly int[]sizes;public readonly int[]parentSizes;public EdgeContainer(int size,bool isDirected){Length=size;IsDirected=isDirected;sizes=new int[size];parentSizes=isDirected?new int[size]:sizes;edges=new List<(int from,TEdge edge)>(size);}[凾(256)]public void Add(int from,TEdge edge){ ++sizes[from];++parentSizes[edge.To];edges.Add((from,edge));}[凾(256)]public CSR<TEdge>ToCSR()=>new CSR<TEdge>(Length,edges);}internal static class GraphBuilderLogic{[凾(512)]public static TGraph ToGraph<TGraph,TNode,TEdge,TOp>(EdgeContainer<TEdge>edgeContainer)where TGraph:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge,IReversable<TEdge>where TOp:struct,IGraphBuildOperator<TGraph,TNode,TEdge>{var op=new TOp();var res=new TNode[edgeContainer.Length];var csr=edgeContainer.ToCSR();var counter=new int[res.Length];var parentCounter=edgeContainer.IsDirected?new int[res.Length]:counter;var children=SizeToArray<TEdge>(edgeContainer.sizes);var parents=edgeContainer.IsDirected?SizeToArray<TEdge>(edgeContainer.parentSizes):children;for(int i=0;i<res.Length;i++){res[i]=op.Node(i,parents[i],children[i]);foreach(var e in csr.EList.AsSpan(csr.Start[i],csr.Start[i+1]-csr.Start[i])){var to=e.To;children[i][counter[i]++]=e;parents[to][parentCounter[to]++]=e.Reversed(i);}}return op.Graph(res,csr);}[凾(512)]public static TGraph ToTree<TGraph,TNode,TEdge,TOp>(EdgeContainer<TEdge>edgeContainer,int root)where TGraph:ITreeGraph<TNode,TEdge>where TNode:class,ITreeNode<TEdge>where TEdge:IGraphEdge,IReversable<TEdge>where TOp:struct,ITreeBuildOperator<TGraph,TNode,TEdge>{var op=new TOp();int size=edgeContainer.Length;var edges=SizeToArray<TEdge>(edgeContainer.sizes);var idxs=new int[edges.Length];foreach(var(from,e)in edgeContainer.edges.AsSpan()){var to=e.To;edges[from][idxs[from]++]=e;edges[to][idxs[to]++]=e.Reversed(from);}idxs.AsSpan().Clear();var sz=new int[size].Fill(1);var children=SizeToArray<TEdge>(edgeContainer.sizes,-1,root);var parent=new int[size];parent[root]=-1;var stack=new Stack<(int Cur,int Chix)>(size);stack.Push((root,0));while(stack.TryPop(out var cur,out var ci)){var es=edges[cur];if( --ci>=0){var tp=es[ci].To;sz[cur]+=sz[tp];if(sz[tp]>sz[es[0].To])(children[cur][0],children[cur][ci])=(children[cur][ci],children[cur][0]);}if( ++ci<children[cur].Length){var to=es[ci].To;if(parent[cur]==to){var b=es.Length-1;(es[ci],es[b])=(es[b],es[ci]);to=es[ci].To;}stack.Push((cur,ci+1));stack.Push((to,0));children[cur][ci]=es[ci];parent[to]=cur;}}var etid=0;var down=new int[size];var up=new int[size];var nxt=new int[size];var nodes=new TNode[size];stack.Push((root,0));while(stack.TryPop(out var cur,out var ci)){var ch=children[cur];if(ci==0){down[cur]=etid++;nodes[cur]=root==cur?op.TreeRootNode(cur,sz[cur],children[cur]):op.TreeNode(cur,sz[cur],nodes[parent[cur]],edges[cur][^1],children[cur]);}if(ci<ch.Length){var to=ch[ci].To;nxt[to]=ci==0?nxt[cur]:to;stack.Push((cur,ci+1));stack.Push((to,0));}else up[cur]=etid;}var hl=new HeavyLightDecomposition<TNode,TEdge>(nodes,nxt,down,up);return op.Tree(nodes,root,hl);}static T[][]SizeToArray<T>(int[]sizeArray,int offset=0,int root=-1){var a=new T[sizeArray.Length][];for(int i=0;i<sizeArray.Length;i++)a[i]=new T[sizeArray[i]+(root==i?0:offset)];return a;}}public static class GraphExtensions{[凾(256)]public static int LowestCommonAncestor<TNode,TEdge>(this ITreeGraph<TNode,TEdge>tree,int u,int v)where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge=>tree.HlDecomposition.LowestCommonAncestor(u,v);}}
namespace Kzrnm.Competitive{public class HeavyLightDecomposition<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{public TNode[]tree;public int[]down;public int[]up;public int[]nxt;public HeavyLightDecomposition(TNode[]tree,int[]nxt,int[]down,int[]up){this.tree=tree;this.nxt=nxt;this.down=down;this.up=up;}[凾(256)]public(int From,int To)Index(int u)=>(down[u],up[u]);[凾(256)]public int LowestCommonAncestor(int u,int v){if(u==v)return u;var f=down[u]+1;var t=down[v]+1;if(t<f)(f,t)=(t,f);return lcaTable[f..t].Node;}[凾(256)]public void PathQuery(int u,int v,bool vertex,Action<int,int>f)=>PathQuery(u,v,vertex,new FWrapper(f));[凾(256)]public void PathQuery<TOp>(int u,int v,bool vertex,TOp f)where TOp:IHlDecompositionOperator{foreach(var(from,to)in new PathEnumerator(this,u,v,vertex))f.Operate(from,to);}[凾(256)]public void PathQuery<TOp>(int u,int v,bool vertex,ref TOp f)where TOp:IHlDecompositionOperator{foreach(var(from,to)in new PathEnumerator(this,u,v,vertex))f.Operate(from,to);}[凾(256)]public void SubtreeQuery(int u,bool vertex,Action<int,int>f)=>SubtreeQuery(u,vertex,new FWrapper(f));[凾(256)]public void SubtreeQuery<TOp>(int u,bool vertex,TOp f)where TOp:IHlDecompositionOperator=>f.Operate(down[u]+(vertex?0:1),up[u]);[凾(256)]public void SubtreeQuery<TOp>(int u,bool vertex,ref TOp f)where TOp:IHlDecompositionOperator=>f.Operate(down[u]+(vertex?0:1),up[u]);private SparseTable<(int Depth,int Node),NodeMinOp>_lcaTable;private SparseTable<(int Depth,int Node),NodeMinOp>lcaTable=>_lcaTable??=BuildLcaTable();private SparseTable<(int Depth,int Node),NodeMinOp>BuildLcaTable(){var arr=new(int Depth,int Node)[down.Length];for(int i=0;i<arr.Length;i++){var n=tree[i];arr[down[i]]=(n.Depth,n.Parent.To);}return new SparseTable<(int Depth,int Node),NodeMinOp>(arr);}private struct NodeMinOp:ISparseTableOperator<(int Depth,int Node)>{[凾(256)]public(int Depth,int Node)Operate((int Depth,int Node)x,(int Depth,int Node)y)=>x.Depth<=y.Depth?x:y;}private readonly struct FWrapper:IHlDecompositionOperator{private readonly Action<int,int>f;public FWrapper(Action<int,int>func){f=func;}[凾(256)]public void Operate(int u,int v)=>f(u,v);}private struct PathEnumerator{HeavyLightDecomposition<TNode,TEdge>hl;(int f,int t)_c;int u,v,lca;Stack<(int f,int t)>desc;St st;public PathEnumerator(HeavyLightDecomposition<TNode,TEdge>hl,int u,int v,bool vertex){lca=hl.LowestCommonAncestor(u,v);desc=BuildDesc(hl,lca,v);_c=default;this.hl=hl;this.u=u;this.v=lca;st=(St)(vertex?0b11:0b01);}public PathEnumerator GetEnumerator()=>this;static Stack<(int f,int t)>BuildDesc(HeavyLightDecomposition<TNode,TEdge>hl,int u,int v){var s=new Stack<(int f,int t)>();var tree=hl.tree;var nxt=hl.nxt;var down=hl.down;while(u!=v){if(nxt[u]==nxt[v]){s.Push((down[u]+1,down[v]+1));break;}else{s.Push((down[nxt[v]],down[v]+1));v=tree[nxt[v]].Parent.To;}}return s;}public(int f,int t)Current=>_c;public bool MoveNext(){var down=hl.down;var nxt=hl.nxt;if(u==v)goto Desc;if(st.HasFlag(St.Start))st&=~St.Start;else u=hl.tree[nxt[u]].Parent.To;if(nxt[u]!=nxt[v]){_c=(down[u]+1,down[nxt[u]]);return true;}if(u!=v){_c=(down[u]+1,down[v]+1);u=v;return true;}Desc:if(st.HasFlag(St.Vertex)){st&=~St.Vertex;var r=hl.down[lca];_c=(r,r+1);return true;}return desc.TryPop(out _c);}[Flags]enum St:byte{Start=1,Vertex=0b10,}}}public interface IHlDecompositionOperator{void Operate(int f,int t);}}
namespace Kzrnm.Competitive{public static class 閉路削除DFS{enum Status{None,Active,Done}[凾(256)]public static(int from,TEdge edges)[]RemoveCycle<TNode,TEdge>(this IGraph<TNode,TEdge>graph)where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{var es=new List<(int from,TEdge edge)>();var g=graph.AsArray();var statuses=new Status[g.Length];var depths=new int[g.Length];var rs=new int[g.Length];rs.AsSpan().Fill(-1);void DFS(Stack<(int v,int childIdx,int prev)>stack){while(stack.TryPop(out var tuple)){var(v,ci,prev)=tuple;if(v<0){v=~v;var e=g[v].Children[ci];var nr=rs[e.To];if(rs[v]<0||nr>=0&&depths[rs[v]]>depths[nr])rs[v]=nr;if(nr<0)es.Add((v,e));stack.Push((v,ci+1,prev));continue;}var children=g[v].Children;if(ci==0){statuses[v]=Status.Active;depths[v]=stack.Count;}if(ci<children.Length){var e=children[ci];var child=e.To;switch(statuses[child]){case Status.None:stack.Push((~v,ci,prev));stack.Push((child,0,v));break;case Status.Active:if(!g[v].IsDirected&&child==prev){stack.Push((v,ci+1,prev));break;}if(depths[v]<depths[child])break;if(rs[v]<0||depths[rs[v]]>depths[child])rs[v]=child;break;default:if(rs[v]<0)es.Add((v,e));stack.Push((v,ci+1,prev));break;}}else{if(rs[v]==v)rs[v]=-1;statuses[v]=Status.Done;}}}var stack=new Stack<(int v,int childIdx,int prev)>();for(var i=0;i<g.Length;i++){if(statuses[i]==Status.None){stack.Clear();stack.Push((i,0,-1));DFS(stack);}}return es.ToArray();}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0