結果
問題 | No.3018 目隠し宝探し |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:24:05 |
言語 | C# (.NET 8.0.404) |
結果 |
RE
|
実行時間 | - |
コード長 | 63,482 bytes |
コンパイル時間 | 10,761 ms |
コンパイル使用メモリ | 171,232 KB |
実行使用メモリ | 53,248 KB |
平均クエリ数 | 2.73 |
最終ジャッジ日時 | 2025-01-25 23:18:02 |
合計ジャッジ時間 | 13,700 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 WA * 5 RE * 1 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (112 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System.ComponentModel;using System.Diagnostics.CodeAnalysis;using System.Numerics;using System.Runtime.CompilerServices;using System.Runtime.InteropServices;using System.Collections;using System.Text;using System.Text.RegularExpressions;using static Tmpl;using static CPDebug;using System.Collections.Specialized;using System.Globalization;using System.Diagnostics;StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));Console.SetOut(writer);//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));//Console.SetIn(reader);Solver.Solve();Console.Out.Flush();public static class Solver{private static readonly AtCoderIO cin = new AtCoderIO();public static unsafe void Solve(){int H = cin.Int();int W = cin.Int();fprint("? 1 1");long d1 = cin.Long();fprint($"? 1 {W}");long d2 = cin.Long();for (int y = 1; y <= H; y++){for (int x = 1; x <= W; x++){//check(dist(x, y, 1, 1));if (dist(x, y, 1, 1) == d1 && dist(x, y, W, 1) == d2){fprint($"! {y} {x}");return;}}}}static long dist(long x1, long y1, long x2, long y2){return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);}}struct Border : IComparable<Border>{public long Y;public bool IsCyan;public Border(long y, bool cyan){Y = y;IsCyan = cyan;}public int CompareTo(Border other){return Y.CompareTo(other.Y);}}// 平衡二分探索木を利用してソートされた集合を管理する.public sealed class Set<T> where T : IComparable<T>{private AVLTree<T> _tree;public T Max => _tree.Max();public T Min => _tree.Min();public int Count => _tree.Count;public Set(){_tree = new();}// 要素を追加する.// O(logN)public void Add(T item){_tree.Add(item);}// 要素を削除する.// O(logN)public void Remove(T item){_tree.Remove(item);}// 要素が含まれているかを返す.// O(logN)public bool Contains(T item){return _tree.Contains(item);}// itemのインデックスを返す.// O(logN)public int IndexOf(T item){return _tree.IndexOf(item);}// 値がvalue以上となる最初のインデックスを返す.public int LowerBound(T value){return _tree.LowerBound(value);}public T LowerBoundValue(T value, T fallback){return _tree.LowerBoundValue(value, fallback);}// インデックスで値を取得する.public T GetByIndex(int index){return _tree.GetByIndex(index);}public void RemoveByIndex(int index){_tree.RemoveByIndex(index);}// 昇順ソートされたリストを返す.public List<T> OrderAscending(){return _tree.OrderAscending();}// 降順ソートされたリストを返す.public List<T> OrderDescending(){return _tree.OrderDescending();}public void DebugPrintTree(){_tree.PrintTree();}}// AVL木, 平衡二分探索木.// 参考: https://zenn.dev/student_blog/articles/670eee14e04d46public sealed class AVLTree<T> where T : IComparable<T>{private sealed class Node{private T _value;private Node _left;private Node _right;private int _bias;private int _height;private int _size;public bool Has2Children => _left is not null && _right is not null;public bool HasOnlyLeft => _left is not null && _right is null;public bool HasOnlyRight => _left is null && _right is not null;public bool HasNoChild => _left is null && _right is null;public Node(T value){_value = value;_left = null;_right = null;_bias = 0;_height = 1;_size = 1;}public T Value{get => _value;set => _value = value;}public Node Left{get => _left;set => _left = value;}public Node Right{get => _right;set => _right = value;}public int Bias{get => _bias;set => _bias = value;}public int Height{get => _height;set => _height = value;}public int Size{get => _size;set => _size = value;}public int LeftHeight() => _left is not null ? _left.Height : 0;public int RightHeight() => _right is not null ? _right.Height : 0;public int LeftSize() => _left is not null ? _left.Size : 0;public int RightSize() => _right is not null ? _right.Size : 0;}private Node _rootNode = null;public int Count => SizeOf(_rootNode);public AVLTree(){_rootNode = null;}public void Add(T value){_rootNode = AddRecursive(_rootNode, value);}public void Remove(T value){_rootNode = RemoveRecursive(_rootNode, value);}private Node RemoveRecursive(Node current, T value){if (current is null){return null;}if (current.Value.CompareTo(value) == 0){// 消すreturn InternalRemoveNode(current);}if (value.CompareTo(current.Value) == -1){current.Left = RemoveRecursive(current.Left, value);Update(current.Left);Update(current);current = Balance(current);Update(current);return current;}else{current.Right = RemoveRecursive(current.Right, value);Update(current.Right);Update(current);current = Balance(current);Update(current);return current;}}private Node InternalRemoveNode(Node target){if (target.Has2Children){Node max = GetMaxNode(target.Left);T val = max.Value;if (target.Left == max){target.Left = target.Left.Left;}else{target.Left = DeleteRightNode(target.Left, max);}target.Value = val;Update(target.Left);Update(target.Right);Update(target);target = Balance(target);Update(target);return target;}else if (target.HasOnlyLeft){target = target.Left;Update(target.Left);Update(target.Right);Update(target);target = Balance(target);Update(target);return target;}else if (target.HasOnlyRight){target = target.Right;Update(target.Left);Update(target.Right);Update(target);target = Balance(target);Update(target);return target;}else{return null;}}private Node AddRecursive(Node current, T value){if (current is null){current = new Node(value);Update(current);return current;}if (value.CompareTo(current.Value) == -1){current.Left = AddRecursive(current.Left, value);Update(current.Left);Update(current);current = Balance(current);Update(current);}else{current.Right = AddRecursive(current.Right, value);Update(current.Right);Update(current);current = Balance(current);Update(current);}return current;}private Node Balance(Node node){if (node.Bias == 0){return node;}if (node.Bias == 1 || node.Bias == -1){return node;}if (node.Bias >= 2){if (node.Left.Bias > 0){node = RotateRight(node);node.Bias = 0;return node;}else{node.Left = RotateLeft(node.Left);node = RotateRight(node);node.Bias = 0;return node;}}else{if (node.Right.Bias < 0){node = RotateLeft(node);node.Bias = 0;return node;}else{node.Right = RotateRight(node.Right);node = RotateLeft(node);node.Bias = 0;return node;}}}private Node DeleteRightNode(Node root, Node target){if (root is null) return null;if (root.Right == target){root.Right = root.Right.Left;Update(root.Right);Update(root);root = Balance(root);Update(root);return root;}else{int sz = root.Size;root.Right = DeleteRightNode(root.Right, target);Update(root.Right);Update(root.Left);Update(root);root = Balance(root);if (sz - root.Size == 2){Console.WriteLine("ERR");}Update(root);return root;}}private Node GetMaxNode(Node node){Node cur = node;while (cur.Right is not null) cur = cur.Right;return cur;}private Node GetMinNode(Node node){Node cur = node;while (cur.Left is not null) cur = cur.Left;return cur;}// 新しい部分木の根を返すprivate Node RotateLeft(Node node){Node right = node.Right;node.Right = right.Left;right.Left = node;Update(right.Left);Update(right.Right);Update(right);return right;}// 新しい部分木の根を返すprivate Node RotateRight(Node node){Node left = node.Left;node.Left = left.Right;left.Right = node;Update(left.Left);Update(left.Right);Update(left);return left;}private void Update(Node node){if (node is null) return;node.Height = HeightOf(node);node.Size = SizeOf(node);node.Bias = node.LeftHeight() - node.RightHeight();}private int HeightOf(Node node){if (node is null) return 0;int left = node.LeftHeight();int right = node.RightHeight();return int.Max(left, right) + 1;}private int SizeOf(Node node){if (node is null) return 0;int left = node.LeftSize();int right = node.RightSize();return left + right + 1;}public void PrintTree(){static void PrintNode(Node node, int depth){if (node is null) return;PrintNode(node.Right, depth + 1);Console.WriteLine(new string('\t', depth) + node.Value + $"({node.Bias}; {node.Height}; {node.Size})");PrintNode(node.Left, depth + 1);}PrintNode(_rootNode, 0);}public bool Contains(T value){Node current = _rootNode;while (current is not null){if (current.Value.CompareTo(value) == 0) return true;if (value.CompareTo(current.Value) == -1) current = current.Left;else current = current.Right;}return false;}public T Max(){return GetMaxNode(_rootNode).Value;}public T Min(){return GetMinNode(_rootNode).Value;}public T GetByIndex(int index){if (_rootNode is null){throw new IndexOutOfRangeException();}if (index < 0 || index >= Count){throw new IndexOutOfRangeException();}return GetByIndexRecursive(_rootNode, index);}public void RemoveByIndex(int index){if (_rootNode is null) return;if (index < 0 || index >= Count){throw new IndexOutOfRangeException();}_rootNode = RemoveByIndexRecursive(_rootNode, index);}private Node RemoveByIndexRecursive(Node current, int offset){if (current is null){Console.WriteLine($"! current was null. offset={offset} count={Count}");return default;}int left = current.LeftSize();if (left == offset){return InternalRemoveNode(current);}if (offset < left){current.Left = RemoveByIndexRecursive(current.Left, offset);Update(current);current = Balance(current);Update(current);return current;}else{current.Right = RemoveByIndexRecursive(current.Right, offset - left - 1);Update(current);current = Balance(current);Update(current);return current;}}private T GetByIndexRecursive(Node current, int offset){if (current is null){Console.WriteLine($"! current was null. offset={offset} count={Count}");return default;}int left = current.LeftSize();if (left == offset){return current.Value;}if (offset < left){return GetByIndexRecursive(current.Left, offset);}else{return GetByIndexRecursive(current.Right, offset - left - 1);}}public int IndexOf(T value){int index = _rootNode.LeftSize();Node current = _rootNode;while (true){// leftint c = value.CompareTo(current.Value);if (c == -1){if (current.Left is null) return -1;else{current = current.Left;index -= current.RightSize() + 1;}}else if (c == 0) return index;else{if (current.Right is null) return -1;else{current = current.Right;index += current.LeftSize() + 1;}}}}public T LowerBoundValue(T value, T fallback){if (_rootNode is null) return fallback;int res = _rootNode.Size;Node current = _rootNode;T lowerbound = default;int index = _rootNode.LeftSize();while (true){int cmp = value.CompareTo(current.Value);if (cmp <= 0){res = int.Min(res, index);lowerbound = current.Value;if (current.Left is null) break;index -= current.Left.RightSize() + 1;current = current.Left;}else{if (current.Right is null) break;index += current.Right.LeftSize() + 1;current = current.Right;}}return res < Count ? lowerbound : fallback;}public int LowerBound(T value){if (_rootNode is null) return 0;int res = _rootNode.Size;Node current = _rootNode;int index = _rootNode.LeftSize();while (true){int cmp = value.CompareTo(current.Value);if (cmp <= 0){res = int.Min(res, index);if (current.Left is null) break;index -= current.Left.RightSize() + 1;current = current.Left;}else{if (current.Right is null) break;index += current.Right.LeftSize() + 1;current = current.Right;}}return res;// Node root = _rootNode;// var torg = root;// if (root is null) return -1;// var idx = root.Size - root.RightSize() - 1;// var ret = Int32.MaxValue;// while (root is not null)// {// if (root.Value.CompareTo(value) >= 0)// {// if (root.Value.CompareTo(value) == 0) ret = int.Min(ret, idx);// root = root.Left;// if (root == null) ret = Math.Min(ret, idx);// idx -= root is null ? 0 : (root.RightSize() + 1);// }// else// {// root = root.Right;// idx += (root is null ? 1 : root.LeftSize() + 1);// if (root == null) return idx;// }// }// return ret == Int32.MaxValue ? torg.Size : ret;}public List<T> OrderAscending(){if (_rootNode is null) return new List<T>();List<T> res = new(_rootNode.Size);void extract(Node node){if (node is null) return;extract(node.Left);res.Add(node.Value);extract(node.Right);}return res;}public List<T> OrderDescending(){if (_rootNode is null) return new List<T>();List<T> res = new(_rootNode.Size);void extract(Node node){if (node is null) return;extract(node.Right);res.Add(node.Value);extract(node.Left);}return res;}}static class Constants{public const long Mod = 998244353L;//public const long Mod = 10007L;//public const long Mod = 1000000007L;}public readonly struct Point{public readonly int X;public readonly int Y;public Point(int x, int y){X = x;Y = y;}public override int GetHashCode() => (X, Y).GetHashCode();public override string ToString(){return $"({X}, {Y})";}}public sealed class ReverseComparer<T> : IComparer<T>{public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);public static ReverseComparer<T> Reverse(IComparer<T> comparer){return new ReverseComparer<T>(comparer);}private readonly IComparer<T> comparer = Default;private ReverseComparer(IComparer<T> comparer){this.comparer = comparer;}public int Compare(T x, T y){return comparer.Compare(y, x);}}public sealed class AtCoderIO{Queue<string> _readQueue = new Queue<string>();private void LoadQueue(){if (_readQueue.Count > 0) return;string line = Console.ReadLine();string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);}private void Guard(){if (_readQueue.Count == 0){throw new Exception("NO DATA TO READ");}}public int Int(){LoadQueue();Guard();return int.Parse(_readQueue.Dequeue());}public long Long(){LoadQueue();Guard();return long.Parse(_readQueue.Dequeue());}public string String(){LoadQueue();Guard();return _readQueue.Dequeue();}public short Short(){LoadQueue();Guard();return short.Parse(_readQueue.Dequeue());}public byte Byte(){LoadQueue();Guard();return byte.Parse(_readQueue.Dequeue());}public char Char(){LoadQueue();Guard();return char.Parse(_readQueue.Dequeue());}public double Double(){LoadQueue();Guard();return double.Parse(_readQueue.Dequeue());}public float Float(){LoadQueue();Guard();return float.Parse(_readQueue.Dequeue());}public ModInt ModInt(){return new ModInt(Long());}public T Read<T>(){Type type = typeof(T);if (type == typeof(int)) return (T)(object)Int();else if (type == typeof(long)) return (T)(object)Long();else if (type == typeof(float)) return (T)(object)Float();else if (type == typeof(double)) return (T)(object)Double();else if (type == typeof(short)) return (T)(object)Short();else if (type == typeof(byte)) return (T)(object)Byte();else if (type == typeof(char)) return (T)(object)Char();else if (type == typeof(string)) return (T)(object)String();else if (type == typeof(ModInt)) return (T)(object)ModInt();else return default(T);}public int[] IntArray(int n){if (n == 0) return Array.Empty<int>();int[] arr = new int[n];for (int i = 0; i < n; i++){arr[i] = Int();}return arr;}public int[] ZeroIndexedPermutation(int n){if (n == 0) return Array.Empty<int>();int[] arr = new int[n];for (int i = 0; i < n; i++){arr[i] = Int() - 1;}return arr;}public long[] LongArray(int n){if (n == 0) return Array.Empty<long>();long[] arr = new long[n];for (int i = 0; i < n; i++){arr[i] = Long();}return arr;}public double[] DoubleArray(int n){if (n == 0) return Array.Empty<double>();double[] arr = new double[n];for (int i = 0; i < n; i++){arr[i] = Double();}return arr;}public ModInt[] ModIntArray(int n){if (n == 0) return Array.Empty<ModInt>();ModInt[] arr = new ModInt[n];for (int i = 0; i < n; i++){arr[i] = (ModInt)Long();}return arr;}public T[] ReadArray<T>(int n){if (n == 0) return Array.Empty<T>();T[] arr = new T[n];for (int i = 0; i < n; i++){arr[i] = Read<T>();}return arr;}}public static class CPDebug{public static void check<T>(T value, [CallerArgumentExpression(nameof(value))] string name = "value"){#if DEBUGConsole.WriteLine($"[DEBUG] {name}={value.ToString()}");#endif}public static void check<T>(IEnumerable<T> value, [CallerArgumentExpression(nameof(value))] string name = "value"){#if DEBUGConsole.WriteLine($"[DEBUG] {name}=({string.Join(' ', value)})");#endif}}public static class Tmpl{public static int combination(int n, int r){int c = 1;for (int i = 1; i <= r; i++){c = c * (n - i + 1) / i;}return c;}public static long combination(long n, long r){long c = 1;for (long i = 1; i <= r; i++){c = c * (n - i + 1) / i;}return c;}public static long pow(long b, long exp){if (exp == 0) return 1;if (exp == 1) return b;long m = pow(b, exp / 2L);m *= m;if (exp % 2L == 1) m *= b;return m;}public static long modpow(long b, long exp, long mod){if (exp == 0) return 1;if (exp == 1) return b % mod;long m = modpow(b, exp / 2L, mod);m *= m;m %= mod;if (exp % 2L == 1) m *= b % mod;m %= mod;return m;}static long modinv( long a, long mod ){long b = mod, u = 1, v = 0;while ( b > 0 ){long t = a / b;a -= t * b; swap( ref a, ref b );u -= t * v; swap( ref u, ref v );}u %= mod;if (u < 0) u += mod;return u;}public static long calcLcm(long a, long b){return a * b / calcGcd(a, b);}public static long calcGcd(long a, long b){if (a % b == 0) return b;return calcGcd(b, a % b);}// ax ≡ b (mod m)なる最小のxを求めるpublic static bool solveModLinear(long a, long b, long m, out long minSolution){long gcd = calcGcd(calcGcd(a, b), m);a /= gcd;b /= gcd;m /= gcd;if (calcGcd(a, m) == 1){long inv = modinv(a, m);minSolution = (b * inv) % m;return true;}minSolution = 0;return false;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void YesNo(bool t){Console.WriteLine(t ? "Yes" : "No");}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void YESNO(bool t){Console.WriteLine(t ? "YES" : "NO");}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void yesno(bool t){Console.WriteLine(t ? "yes" : "no");}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static bool checkBit(int bit, int n){return ((1 << n) & bit) != 0;}public static bool nextCombination(int n, int r, int[] array){int i = array.Length - 1;while (i >= 0 && array[i] == i + n - r){i--;}if (i < 0) return false;array[i]++;for (int j = i + 1; j < r; j++){array[j] = array[j - 1] + 1;}return true;}public static bool nextPermutation<T>(T[] array, int start, int length) where T : IComparable<T>{int end = start + length - 1;if (end <= start) return false;int last = end;while (true){int pos = last--;if (array[last].CompareTo(array[pos]) < 0){int i;for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }T tmp = array[last]; array[last] = array[i]; array[i] = tmp;Array.Reverse(array, pos, end - pos + 1);return true;}if (last == start){Array.Reverse(array, start, end - start);return false;}}throw new Exception("NextPermutation: Fatal error");}public static unsafe Dictionary<char, int> cntCharOcc(string s){Dictionary<char, int> dict = new Dictionary<char, int>();fixed (char* ptr = s){for (int i = 0; i < s.Length; i++){if (dict.ContainsKey(ptr[i])){dict[ptr[i]] += 1;}else{dict[ptr[i]] = 1;}}}return dict;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void chmax<T> (ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>{if (value > target){target = value;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void chmin<T>(ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>{if (value < target){target = value;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void arrMod<T>(T[] array, T b) where T : IModulusOperators<T, T, T>{for (int i = 0; i < array.Length; i++){array[i] %= b;}}public static ReadOnlySpan<T> spanOf<T>(List<T> list){return CollectionsMarshal.AsSpan(list);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void swap<T>(T[] array, int i, int j) where T : struct{(array[i], array[j]) = (array[j], array[i]);}public static void shuffle<T>(T[] array) where T : struct{Random random = new Random();for (int i = array.Length - 1; i > 0; i--){int index = random.Next(0, i + 1);swap(array, index, i);}}public static int lowerBound<T>(T[] array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>{int low = start;int high = end;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (array[mid] < value)low = mid + 1;elsehigh = mid;}if (low == array.Length - 1 && array[low] < value){return array.Length;}return low;}public static int lowerBound<T>(List<T> array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>{int low = start;int high = end;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (array[mid] < value)low = mid + 1;elsehigh = mid;}if (low == array.Count - 1 && array[low] < value){return array.Count;}return low;}public static int upperBound<T>(T[] array, T value) where T : struct, IComparisonOperators<T, T, bool>{var l = 0;var r = array.Length - 1;while (l <= r){var mid = l + (r - l) / 2;if (array[mid] <= value) l = mid + 1;else r = mid - 1;}return l;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void swap<T>(ref T a, ref T b) where T : struct{T temp = a;a = b;b = temp;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static bool dbleq(double a, double b){return Math.Abs(a - b) < double.Epsilon;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int dblAsInt(double d){return (int)Math.Round(d, 0);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static long dblAsLong(double d){return (long)Math.Round(d, 0);}public static int[] compressCoords<T>(T[] a) where T : struct, IComparisonOperators<T, T, bool>{T[] b = a.OrderBy(x => x).Distinct().ToArray();int[] result = new int[a.Length];for (int i = 0; i < a.Length; i++){result[i] = lowerBound(b, 0, b.Length - 1, a[i]);}return result;}public static List<RunLengthElement<T>> compressRunLength<T>(T[] array) where T : struct, IEquatable<T>{List<RunLengthElement<T>> list = new List<RunLengthElement<T>>();int count = 1;int start = 0;T prev = array[0];for (int i = 1; i < array.Length; i++){if (prev.Equals(array[i])){count++;}else{list.Add(new RunLengthElement<T>(start, count, prev));start = i;count = 1;}prev = array[i];}list.Add(new RunLengthElement<T>(start, count, prev));return list;}public static char[] alphabetsLower(){return new[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y','z' };}public static char[] alphebetsUpper(){return new[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y','Z'};}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void print<T>(IEnumerable<T> array, char delimiter = ' '){Console.WriteLine(string.Join(delimiter, array));}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void fprint<T>(IEnumerable<T> array, char delimiter = ' '){print(array);Console.Out.Flush();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void print(string msg){Console.WriteLine(msg);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void fprint(string msg){Console.WriteLine(msg);Console.Out.Flush();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void print(int val){print(val.ToString());}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void print(long val){print(val.ToString());}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void print(ModInt val){print(val.ToString());}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void fprint(int val){print(val.ToString());Console.Out.Flush();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void fprint(long val){print(val.ToString());Console.Out.Flush();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static void fprint(ModInt val){fprint(val.ToString());Console.Out.Flush();}public static void print<T>(T[,] grid){for (int y = 0; y < grid.GetLength(0); y++){for (int x = 0; x < grid.GetLength(1); x++){Console.Write(grid[y, x] + "\t");}Console.WriteLine();}}public static void print01(bool t){Console.WriteLine(t ? "1" : "0");}public static TSrc lowerBoundKth<TSrc, TCnt>(TSrc min, TSrc max, Func<TSrc, TCnt> f, TCnt bound)where TSrc: struct, INumber<TSrc> where TCnt: struct, INumber<TCnt>{TSrc left = min;TSrc right = max;TSrc two = TSrc.CreateChecked(2);TSrc one = TSrc.CreateChecked(1);while (right > left){TSrc mid = left + (right - left) / two;TCnt c = f(mid);if (c < bound){left = mid + one;}else{right = mid;}}return left;}public static bool isSquareNumber(long n){long q = (long)Math.Floor(Math.Sqrt(n));return q * q == n;}}public readonly struct RunLengthElement<T> where T : struct{public readonly int Count;public readonly int StartIndex;public readonly T Value;public RunLengthElement(int startIndex, int count, T value){this.StartIndex = startIndex;this.Count = count;this.Value = value;}}public readonly struct Edge<T> : IEquatable<Edge<T>>, IComparable<Edge<T>> where T : struct, INumber<T>{public readonly int To;public readonly int From;public readonly T Weight;public Edge(int to, T weight){this.To = to;this.Weight = weight;}public Edge(int from, int to, T weight){this.To = to;this.From = from;this.Weight = weight;}public override bool Equals(object obj){if (obj is Edge<T> edge){return this.Equals(edge);}else{return false;}}public int CompareTo(Edge<T> other){return Weight.CompareTo(other.Weight);}public bool Equals(Edge<T> edge){return To == edge.To && From == edge.From && Weight == edge.Weight;}public override int GetHashCode(){return (To, From, Weight).GetHashCode();}public static bool operator ==(Edge<T> left, Edge<T> right){return left.Equals(right);}public static bool operator !=(Edge<T> left, Edge<T> right){return !left.Equals(right);}}public readonly struct ModInt : IEquatable<ModInt>, IAdditionOperators<ModInt, ModInt, ModInt>, ISubtractionOperators<ModInt, ModInt, ModInt>,IAdditiveIdentity<ModInt, ModInt>{private readonly long Value;public static ModInt One => (ModInt)1L;public static ModInt Zero => (ModInt)0L;public static ModInt AdditiveIdentity => Zero;public ModInt(long value){Value = SafeMod(value);}[MethodImpl(MethodImplOptions.AggressiveInlining)]private static long SafeMod(long a){a %= Constants.Mod;if (a < 0) a += Constants.Mod;return a;}public ModInt Power(long exp){if (exp <= -1) return this;if (exp == 0) return 1;if (exp == 1) return this;ModInt m = Power(exp / 2);m *= m;if (exp % 2 == 1) m *= this;return m;}public ModInt Inv(){return this.Power(Constants.Mod - 2L);}public static ModInt operator +(ModInt left, ModInt right){return new ModInt(SafeMod(left.Value + right.Value));}public static ModInt operator -(ModInt left, ModInt right){return new ModInt(SafeMod(left.Value - right.Value));}public static ModInt operator *(ModInt left, ModInt right){return new ModInt(SafeMod(left.Value * right.Value));}public static ModInt operator /(ModInt left, ModInt right){if (right.Value == 0L){return Zero;}ModInt inv = right.Inv();return SafeMod(left * inv);}public static ModInt operator %(ModInt left, ModInt right){if (right.Value == 0L){return Zero;}return new ModInt(SafeMod(left.Value % right.Value));}public static bool operator ==(ModInt left, ModInt right){return left.Value == right.Value;}public static bool operator != (ModInt left, ModInt right){return !(left == right);}public bool Equals(ModInt other){return Value == other.Value;}public override bool Equals(object other){if (other is ModInt m){return this == m;}else return false;}public override int GetHashCode(){return Value.GetHashCode();}public static implicit operator ModInt(long v){return new ModInt(v);}public static implicit operator ModInt(int v){return new ModInt(v);}public static implicit operator long(ModInt m){return m.Value;}public static implicit operator int(ModInt m){return (int)m.Value;}public long Raw() => Value;public override string ToString(){return Value.ToString();}}public delegate T Monoid<T>(T a, T b);public delegate T Apply<T, M>(T x, M m, int len);// 一点に対する操作と区間に対するクエリを処理する.// 空間計算量: O(2N)// 時間計算量:// - 構築: O(N)// - 操作: O(logN)// - クエリ: O(logN)public sealed class SegmentTree<T> where T : struct{private int _treeSize;private int _dataSize;private int _originalDataSize;private T[] _data;private Monoid<T> _operator;private Monoid<T> _apply;private T _identity;public int OriginalDataSize => _originalDataSize;public int TreeSize => _treeSize;public T Identity => _identity;public T this[int index]{get{return _data[_dataSize - 1 + index];}}public SegmentTree(int n, Monoid<T> op, Monoid<T> apply, T identity){_originalDataSize = n;int size = 1;while (n > size){size <<= 1;}_dataSize = size;_treeSize = 2 * size - 1;_data = new T[_treeSize];_identity = identity;_operator = op;_apply = apply;}public void Build(T[] array){for (int i = 0; i < array.Length; i++){_data[i + _dataSize - 1] = array[i];}for (int i = _dataSize - 2; i >= 0; i--){_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);}}public void Apply(int index, T value){index += _dataSize - 1;_data[index] = _apply(_data[index], value);while (index > 0){index = (index - 1) >> 1;_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);}}public T Query(int left, int right){return QueryRec(left, right, 0, 0, _dataSize);}private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight){if (left >= nodeRight || right <= nodeLeft){return _identity;}if (left <= nodeLeft && nodeRight <= right){return _data[index];}T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);return _operator(leftChild, rightChild);}// 返されたArraySegment<T>は変更してはいけない.public ArraySegment<T> GetData(){return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);}}// 区間に対する操作と区間に対するクエリを処理する.// 空間計算量: O(4N)// 時間計算量:// - 構築: O(N)// - 操作: O(logN)// - クエリ: O(logN)// - 一点参照: O(logN)// operator: クエリに対応する二項演算をする// mapping: 作用素を作用させる// composition: 作用素を合成するpublic sealed class LazySegmentTree<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>{private int _treeSize;private int _dataSize;private int _originalDataSize;private T[] _data;private M?[] _lazy;private Monoid<T> _operator;private Apply<T, M> _mapping;private Monoid<M> _composition;private T _identity;public T this[int index]{get{return GetByIndex(index);}}public LazySegmentTree(int n, Monoid<T> op, Apply<T, M> mapping, Monoid<M> composition, T identity){_originalDataSize = n;int size = 1;while (n > size){size <<= 1;}_dataSize = size;_treeSize = 2 * size - 1;_data = new T[_treeSize];_data.AsSpan().Fill(_identity);_lazy = new M?[_treeSize];_identity = identity;_operator = op;_mapping = mapping;_composition = composition;}public void Build(T[] array){for (int i = 0; i < array.Length; i++){_data[i + _dataSize - 1] = array[i];}for (int i = _dataSize - 2; i >= 0; i--){_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);}}private void Evaluate(int index, int l, int r){if (_lazy[index] is null){return;}if (index < _dataSize - 1){_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);}_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);_lazy[index] = null;}private M GuardComposition(M? a, M? b){if (a is null){return (M)b;}else{return _composition((M)a, (M)b);}}private void ApplyRec(int a, int b, M m, int index, int l, int r){Evaluate(index, l, r);if (a <= l && r <= b){_lazy[index] = GuardComposition(_lazy[index], m);Evaluate(index, l, r);}else if (a < r && l < b){ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);}}public void Apply(int left, int right, M m){ApplyRec(left, right, m, 0, 0, _dataSize);}public T Query(int left, int right){return QueryRec(left, right, 0, 0, _dataSize);}private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight){Evaluate(index, nodeLeft, nodeRight);if (left >= nodeRight || right <= nodeLeft){return _identity;}if (left <= nodeLeft && nodeRight <= right){return _data[index];}T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);return _operator(leftChild, rightChild);}public T GetByIndex(int target){if (target < 0 || target >= _originalDataSize){throw new Exception("Index is out of range.");}return AccessRec(target, 0, 0, _dataSize);}private T AccessRec(int target, int index, int l, int r){Evaluate(index, l, r);if (index >= _dataSize - 1){return _data[index];}int mid = (l + r) / 2;if (target < mid){return AccessRec(target, (index << 1) + 1, l, mid);}else{return AccessRec(target, (index << 1) + 2, mid, r);}}// index以下のノードをすべて即時に評価する.private void EvaluateAll(int index, int l, int r){if (_lazy[index] is null){if (index < _dataSize - 1){EvaluateAll((index << 1) + 1, l, (l + r) / 2);EvaluateAll((index << 1) + 2, (l + r) / 2, r);}return;}if (index < _dataSize - 1){_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);EvaluateAll((index << 1) + 1, l, (l + r) / 2);EvaluateAll((index << 1) + 2, (l + r) / 2, r);}_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);_lazy[index] = null;}// 返されたArraySegment<T>は変更してはいけない.public ArraySegment<T> GetData(){EvaluateAll(0, 0, _dataSize);return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);}}public struct BeatsNode<T> where T : struct, IEquatable<T>{public T Value;public bool Failed;public BeatsNode(T value){Failed = false;Value = value;}}// 区間に対する操作と区間に対するクエリを処理する.// 空間計算量: O(4N)// 時間計算量:// - 構築: O(N)// - 操作: (操作に依存した計算量)// - クエリ: O(logN)// operator: クエリに対応する二項演算をする. 必ず計算ができる必要がある.// mapping: 作用素を作用させる. 計算が出来なければFailed←trueとして返す. この際, 子ノードに対する評価が実行される.// composition: 作用素を合成するpublic sealed class SegmentTreeBeats<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>{private int _treeSize;private int _dataSize;private int _originalDataSize;private BeatsNode<T>[] _data;private M?[] _lazy;private Monoid<BeatsNode<T>> _operator;private Apply<BeatsNode<T>, M> _mapping;private Monoid<M> _composition;private T _identity;private BeatsNode<T> _identityNode;public T this[int index]{get{return GetByIndex(index);}}public SegmentTreeBeats(int n, Monoid<BeatsNode<T>> op, Apply<BeatsNode<T>, M> mapping, Monoid<M> composition, T identity){_originalDataSize = n;int size = 1;while (n > size){size <<= 1;}_dataSize = size;_treeSize = 2 * size - 1;_data = new BeatsNode<T>[_treeSize];_identityNode = new BeatsNode<T>(_identity);_data.AsSpan().Fill(_identityNode);_lazy = new M?[_treeSize];_identity = identity;_operator = op;_mapping = mapping;_composition = composition;}public void Build(T[] array){for (int i = 0; i < array.Length; i++){_data[i + _dataSize - 1] = new BeatsNode<T>(array[i]);}for (int i = _dataSize - 2; i >= 0; i--){_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);}}private void Evaluate(int index, int l, int r){if (_lazy[index] is null){return;}if (index < _dataSize - 1){//_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);//_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);if (_lazy[(index << 1) + 1] is not null){Evaluate((index << 1) + 1, l, (l + r) / 2);}_lazy[(index << 1) + 1] = _lazy[index];if (_lazy[(index << 1) + 2] is not null){Evaluate((index << 1) + 2, (l + r) / 2, r);}_lazy[(index << 1) + 2] = _lazy[index];}//_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);// 計算してみるBeatsNode<T> val = _mapping(_data[index], (M)_lazy[index], r - l);// 計算出来なければif (val.Failed){if (index >= _dataSize - 1){throw new Exception("葉ノードに対するmappingは失敗してはいけません");}// 子ノードを即評価Evaluate((index << 1) + 1, l, (l + r) / 2);Evaluate((index << 1) + 2, (l + r) / 2, r);// 子ノードの結果から親を更新_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);}else{// 計算できればそのまま更新_data[index] = val;}_lazy[index] = null;}private M GuardComposition(M? a, M? b){if (a is null){return (M)b;}else{return _composition((M)a, (M)b);}}private void ApplyRec(int a, int b, M m, int index, int l, int r){Evaluate(index, l, r);if (a <= l && r <= b){_lazy[index] = GuardComposition(_lazy[index], m);Evaluate(index, l, r);}else if (a < r && l < b){ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);}}public void Apply(int left, int right, M m){ApplyRec(left, right, m, 0, 0, _dataSize);}public T Query(int left, int right){return QueryRec(left, right, 0, 0, _dataSize).Value;}private BeatsNode<T> QueryRec(int left, int right, int index, int nodeLeft, int nodeRight){Evaluate(index, nodeLeft, nodeRight);if (left >= nodeRight || right <= nodeLeft){return _identityNode;}if (left <= nodeLeft && nodeRight <= right){return _data[index];}BeatsNode<T> leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);BeatsNode<T> rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);return _operator(leftChild, rightChild);}public T GetByIndex(int target){if (target < 0 || target >= _originalDataSize){throw new Exception("Index is out of range.");}return AccessRec(target, 0, 0, _dataSize);}private T AccessRec(int target, int index, int l, int r){Evaluate(index, l, r);if (index >= _dataSize - 1){return _data[index].Value;}int mid = (l + r) / 2;if (target < mid){return AccessRec(target, (index << 1) + 1, l, mid);}else{return AccessRec(target, (index << 1) + 2, mid, r);}}// index以下のノードをすべて即時に評価する.private void EvaluateAll(int index, int l, int r){if (_lazy[index] is null){if (index < _dataSize - 1){EvaluateAll((index << 1) + 1, l, (l + r) / 2);EvaluateAll((index << 1) + 2, (l + r) / 2, r);}return;}if (index < _dataSize - 1){//_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);//_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);if (_lazy[(index << 1) + 1] is not null){Evaluate((index << 1) + 1, l, (l + r) / 2);}_lazy[(index << 1) + 1] = _lazy[index];if (_lazy[(index << 1) + 2] is not null){Evaluate((index << 1) + 2, (l + r) / 2, r);}_lazy[(index << 1) + 2] = _lazy[index];EvaluateAll((index << 1) + 1, l, (l + r) / 2);EvaluateAll((index << 1) + 2, (l + r) / 2, r);}_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);_lazy[index] = null;}// 返されたArraySegment<T>は変更してはいけない.public void GetData(T[] destination){if (destination.Length < _originalDataSize){throw new Exception("書き込み先配列の大きさが足りない");}EvaluateAll(0, 0, _dataSize);//return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);for (int i = 0; i < _originalDataSize; i++){destination[i] = _data[_dataSize - 1 + i].Value;}}}public struct ChangeNode<T> : IEquatable<ChangeNode<T>> where T : struct, INumber<T>, IMinMaxValue<T>{public T Max;public int MaxCount;public T SecondMax;public T Min;public int MinCount;public T SecondMin;public T Sum;public bool Equals(ChangeNode<T> other){return this.Equals(other);}public static ChangeNode<R> MakeLeaf<R>(R value) where R : struct, INumber<R>, IMinMaxValue<R>{return new ChangeNode<R>(){Max = value,MaxCount = 1,SecondMax = R.MinValue,Min = value,MinCount = 1,SecondMin = R.MaxValue,Sum = value};}}public static class SegmentTreeBuilder{public static LazySegmentTree<T, T> RangeAddMax<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, T.Max,(x, m, l) =>{return x + m;},(a, b) => { return a + b; },identity);}public static LazySegmentTree<T, T> RangeUpdateMax<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, T.Max,(x, m, l) =>{return m;},(x, y) => { return y; },identity);}public static LazySegmentTree<T, T> RangeAddMin<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, T.Min,(x, m, l) =>{return x + m;},(a, b) => { return a + b; },identity);}public static LazySegmentTree<T, T> RangeUpdateMin<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, T.Min,(x, m, l) =>{return m;},(x, y) => { return y; },identity);}public static LazySegmentTree<T, T> RangeAddSum<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, (x, y) => x + y,(x, m, l) =>{return x + m * T.CreateChecked(l);},(a, b) => { return a + b; },identity);}public static LazySegmentTree<T, T> RangeUpdateSum<T>(int n, T identity) where T : struct, INumber<T>{return new LazySegmentTree<T, T>(n, (x, y) => x + y,(x, m, l) =>{return m * T.CreateChecked(l);},(a, b) => { return b; },identity);}public static SegmentTree<T> PointUpdateMax<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, T.Max, (a, b) => b, identity);}public static SegmentTree<T> PointAddMax<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, T.Max, (a, b) => a + b, identity);}public static SegmentTree<T> PointUpdateMin<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, T.Min, (a, b) => b, identity);}public static SegmentTree<T> PointAddMin<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, T.Min, (a, b) => a + b, identity);}public static SegmentTree<T> PointUpdateSum<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => b, identity);}public static SegmentTree<T> PointAddSum<T>(int n, T identity) where T : struct, INumber<T>{return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => a + b, identity);}}public sealed class PrefixSum2D<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>{private T[,] _sums;public PrefixSum2D(T[,] sequence){int height = sequence.GetLength(0);int width = sequence.GetLength(1);_sums = new T[height + 1, width + 1];// build prefix sumfor (int y = 0; y < height; y++){for (int x = 0; x < width; x++){_sums[y + 1, x + 1] = _sums[y + 1, x] + _sums[y, x + 1] - _sums[y, x] + sequence[y, x];}}}public T Sum(int startInclX, int startInclY, int endExclX, int endExclY){return _sums[endExclY, endExclX] + _sums[startInclY, startInclX] - _sums[startInclY, endExclX] - _sums[endExclY, startInclX];}public T AllSum(){return _sums[_sums.GetLength(0) - 1, _sums.GetLength(1) - 1];}}public sealed class PrefixSum<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T>{private T[] _sums;public PrefixSum(T[] sequence){_sums = new T[sequence.Length + 1];_sums[0] = T.AdditiveIdentity;for (int i = 0; i < sequence.Length; i++){_sums[i + 1] = _sums[i] + sequence[i];}}// [a, b)public T Sum(int aIncl, int bExcl){return _sums[bExcl] - _sums[aIncl];}public T AllSum(){return _sums[^1];}public T[] GetArray(){return _sums;}}public sealed class UnionFind{private int[] _parents;private int[] _size;private int _vertexCount;public int VertexCount => _vertexCount;public UnionFind(int n){_vertexCount = n;_parents = new int[n];_size = new int[n];for (int i = 0; i < n; i++){_parents[i] = i;_size[i] = 1;}}public int Root(int x){if (_parents[x] == x)return x;return _parents[x] = Root(_parents[x]);}public void Unite(int x, int y){int rootX = Root(x);int rootY = Root(y);if (rootX == rootY)return;int from = rootX;int to = rootY;// merge from to toif (_size[from] > _size[to]){(from, to) = (to, from);}_size[to] += _size[from];_parents[from] = to;}public List<int> Find(int x){int rootX = Root(x);List<int> set = new List<int>();for (int i = 0; i < _vertexCount; i++){if (Root(i) == rootX)set.Add(i);}return set;}public Dictionary<int, List<int>> FindAll(){Dictionary<int, List<int>> sets = new Dictionary<int, List<int>>();for (int i = 0; i < _vertexCount; i++){int root = Root(i);if (sets.ContainsKey(root))sets[root].Add(i);elsesets[root] = new List<int>() { i };}return sets;}public bool Same(int x, int y){int rootX = Root(x);int rootY = Root(y);return rootX == rootY;}public int Size(int v){return _size[Root(v)];}public void Clear(){for (int i = 0; i < _vertexCount; i++){_parents[i] = i;}}}