E - Cables and Servers
Source: atcoder
Difficulty: 450

Problem Statement
There are
N
servers numbered from
1
to
N
and
M
cables numbered from
1
to
M
.
Cable
i
connects servers
A_i
and
B_i
bidirectionally.
By performing the following operation some number of times (possibly zero), make all servers connected via cables.
Operation: Choose one cable and reconnect one of its ends to a different server.
Find the minimum number of operations required and output an operation sequence achieving this minimum.
Constraints
2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i, B_i \leq N
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
A_1
B_1
A_2
B_2
\vdots
A_M
B_M
Output
Let the minimum number of operations be
K
. Print
K+1
lines.
The first line should contain
K
.
The
(i+1)
-th line should contain three space-separated integers: the number of the cable chosen in the
i
-th operation, the server number that was originally connected at that end, and the server number to which it is connected after the operation, in this order.
If there are multiple valid solutions, any one of them will be accepted.
Sample Input 1
4 5
1 1
1 2
2 1
3 4
4 4
Sample Output 1
1
1 1 3
By reconnecting the end of cable
1
that is connected to server
1
to server
3
, the servers can be connected via cables.
Operations such as reconnecting the end of cable
5
that is connected to server
4
to server
1
, or reconnecting the end of cable
2
that is connected to server
2
to server
3
, will also result in all servers being connected and are considered correct.
Sample Input 2
4 3
3 4
4 1
1 2
Sample Output 2
0
No operation may be necessary.
Sample Input 3
5 4
3 3
3 3
3 3
3 3
Sample Output 3
4
1 3 5
2 3 4
3 3 2
4 3 1

C++ solution:
#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;

struct DSU
{
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n)
    {
        init(n);
    }
    void init(int n)
    {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x)
    {
        return siz[find(x)];
    }
};
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
    }
    vector<int> vis(m);
    DSU dsu(n);
    int ans = n - 1;
    for (int i = 0; i < m; i++)
    {
        if (!dsu.same(a[i], b[i]))
        {
            dsu.merge(a[i], b[i]);
            ans--;
            vis[i] = true;
        }
    }
    cout << ans << '\n';
    for (int i = 0, j = 0; i < m and ans > 0; i++)
    {
        if (vis[i])
            continue;
        while (dsu.same(j, a[i]))
            j++;
        cout << i + 1 << " " << b[i] + 1 << " " << j + 1 << '\n';
        dsu.merge(a[i], j);
        ans--;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--)
    {
        solve();
    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	n, m := InputInt(), InputInt()
	uf := UnionFind(n)
	a, b := make([]int, m), make([]int, m)
	v := make([]tuple, 0, m)
	for i := 0; i < m; i++ {
		a[i], b[i] = InputInt(), InputInt()
		a[i]--
		b[i]--
		if uf.Root(a[i]) == uf.Root(b[i]) {
			v = append(v, tuple{idx: i, s: a[i], t: b[i]})
		} else {
			uf.Merge(a[i], b[i])
		}
	}
	for i := 0; i < len(v); i++ {
		v[i].r = uf.Root(v[i].s)
	}
	sort.Slice(v, func(i, j int) bool {
		return v[i].r < v[j].r
	})

	roots := make([]int, 0, n)
	for i := 0; i < n; i++ {
		if i == uf.Root(i) {
			roots = append(roots, i)
		}
	}

	rest := make([]int, len(roots))
	for i := 0; i < len(roots); i++ {
		rest[i] = roots[i]
	}

	OutInt(len(roots) - 1)
	for i := 0; i < len(roots)-1; i++ {
		// fmt.Fprintln(wt, rest)
		if uf.Root(v[i].s) == rest[0] {
			for uf.Root(v[i].s) == rest[0] {
				tmp := rest[0]
				rest = rest[1:]
				rest = append(rest, tmp)
			}
			//fmt.Fprintln(wt, "rest =", rest)
			fmt.Fprintln(wt, v[i].idx+1, v[i].s+1, rest[0]+1)
			rest = rest[1:]
		} else {
			fmt.Fprintln(wt, v[i].idx+1, v[i].s+1, rest[0]+1)
			rest = rest[1:]
		}
	}

}

type tuple struct {
	idx int
	s   int
	t   int
	r   int // root
}

type uf_type struct {
	par []int
	siz []int
}

func UnionFind(n int) *uf_type {
	par := make([]int, n)
	siz := make([]int, n)
	for i := 0; i < n; i++ {
		par[i] = -1
		siz[i] = 1
	}
	return &uf_type{par, siz}
}

func (uf *uf_type) Root(x int) int {
	if uf.par[x] == -1 {
		return x
	}
	uf.par[x] = uf.Root(uf.par[x])
	return uf.par[x]
}

func (uf *uf_type) IsSame(x, y int) bool {
	return uf.Root(x) == uf.Root(y)
}

func (uf *uf_type) Merge(x, y int) {
	x = uf.Root(x)
	y = uf.Root(y)
	if x == y {
		return
	}
	if uf.siz[x] < uf.siz[y] {
		x, y = y, x
	}
	uf.par[y] = x
	uf.siz[x] += uf.siz[y]
}

func (uf *uf_type) Size(x int) int {
	return uf.siz[uf.Root(x)]
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.IntFunction;
import java.util.function.Supplier;
import java.util.stream.IntStream;

import static java.lang.Math.*;
import static java.util.Arrays.setAll;
import static java.util.Arrays.sort;

public class Main {

	private static final FastScanner sc = new FastScanner();
	private static final FastPrinter out = new FastPrinter(false);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int m = sc.nextInt();
		UnionFind nodes = new UnionFind(n);
		HashSet<Integer> roots = new HashSet<>(n);
		for (int i = 0; i < n; i++) {
			roots.add(i);
		}
		List<Pair> pairList = new ArrayList<>(m);
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			if (nodes.isConnected(a, b)) {
				pairList.add(new Pair(i, a, b));
			} else {
				int findA = nodes.find(a);
				int findB = nodes.find(b);
				nodes.union(a, b);
				if (findA == nodes.find(a)) {
					roots.remove(findB);
				} else {
					roots.remove(findA);
				}
			}
		}
		out.ensureCapacity(nodes.groupCount() * 6);
		out.println(nodes.groupCount() - 1);
		int i = 0;
		int a = nodes.find(0);
		for (int r: roots) {
			if (r == a) continue;
			Pair pair = pairList.get(i);
			if (nodes.isConnected(pair.a, r)) {
				nodes.union(a, pair.a);
				out.print(pair.i + 1 + " ");
				out.print(pair.a + 1 + " ");
				out.println(1);
			} else {
				nodes.union(pair.a, r);
				out.print(pair.i + 1 + " ");
				out.print(pair.a + 1 + " ");
				out.println(r + 1);
			}
			i++;
		}
		out.flush();
	}

	private static class Pair {
		int i, a, b;
		Pair(int i, int a, int b) {
			this.i = i;
			this.a = a;
			this.b = b;
		}
	}

	/**
	 * int型RingBufferクラス: 固定長の循環バッファを実装
	 */
	@SuppressWarnings("unused")
	private static final class RingBuffer {
		private final int size; // バッファの最大サイズ
		private final int[] buf; // データを格納する配列
		private int head, tail; // データの先頭と末尾を示すインデックス
		private int len; // バッファ内の現在のデータ数

		/**
		 * 指定されたサイズで新しいRingBufferを初期化します。
		 *
		 * @param n バッファの最大サイズ。(int)
		 * @throws IllegalArgumentException サイズが0以下の場合
		 */
		public RingBuffer(int n) {
			if (n <= 0)
				throw new IllegalArgumentException();
			size = n;
			buf = new int[size];
			len = head = tail = 0;
		}

		/**
		 * バッファの末尾に要素を追加します。
		 *
		 * @param e 追加する要素
		 * @return バッファに正常に追加された場合はtrueを返します。 すでに満杯の場合はfalseを返します。
		 */
		public boolean addLast(int e) {
			if (isFull())
				return false;
			buf[tail] = e;
			tail = mod(tail + 1, size);
			len++;
			return true;
		}

		/**
		 * バッファの先頭に要素を追加
		 *
		 * @param e 追加する要素
		 * @return バッファに正常に追加された場合はtrueを返します。 すでに満杯の場合はfalseを返します。
		 */
		public boolean addFirst(int e) {
			if (isFull())
				return false;
			head = mod(head - 1, size);
			buf[head] = e;
			len++;
			return true;
		}

		/**
		 * 指定したインデックスの要素を取得します。
		 * <p>
		 * 負のインデックスは末尾からの相対位置を表す。
		 *
		 * @param index 取得する要素のインデックス。-len <= index < lenを満たす必要があります。
		 * @return 指定されたインデックスの要素
		 * @throws RingBufferIndexException バッファが空の場合、またはインデックスが範囲外の場合
		 */
		public int get(int index) {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			if (index >= len || index < -len)
				throw new RingBufferIndexException(index, -len, len - 1);
			if (index < 0)
				index += len;
			index = mod(index + head, size);
			return buf[index];
		}

		/**
		 * 末尾の要素を取得して削除します。
		 *
		 * @return 末尾の要素
		 * @throws RingBufferIndexException バッファが空の場合
		 */
		public int pollLast() {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			int last = buf[mod(tail - 1, size)];
			len--;
			tail = mod(tail - 1, size);
			return last;
		}

		/**
		 * 先頭の要素を取得して削除します。
		 *
		 * @return 先頭の要素
		 * @throws RingBufferIndexException バッファが空の場合
		 */
		public int pollFirst() {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			int first = buf[head];
			len--;
			head = mod(head + 1, size);
			return first;
		}

		/**
		 * 末尾の要素を取得します。
		 *
		 * @return 末尾の要素
		 * @throws RingBufferIndexException バッファが空の場合
		 */
		public int peekLast() {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			return buf[mod(tail - 1, size)];
		}

		/**
		 * 先頭の要素を取得します。
		 *
		 * @return 先頭の要素
		 * @throws RingBufferIndexException バッファが空の場合
		 */
		public int peekFirst() {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			return buf[head];
		}

		/**
		 * 指定されたインデックスの要素を上書きします。 インデックスが現在の長さと等しい場合、新しい要素を末尾に追加します。
		 *
		 * @param index 上書きする要素のインデックス。-len <= index <= lenを満たす必要があります。
		 * @param e     新しい要素
		 * @return このインスタンス自体を返します。
		 * @throws RingBufferIndexException バッファが空の場合、またはインデックスが範囲外の場合
		 */
		public RingBuffer set(int index, int e) {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty.");
			if (index > len || index < -len)
				throw new RingBufferIndexException(index, -len, len);
			if (index == len) {
				addLast(e);
			} else {
				if (index < 0)
					index += len;
				index = mod(index + head, size);
				buf[index] = e;
			}
			return this;
		}

		/**
		 * 現在のバッファの長さを変更します。 長さが増加する場合、新しい位置には0が挿入されます。
		 *
		 * @param len 新しい長さ（0 <= len <= sizeを満たす必要があります）
		 * @return このインスタンス自体を返します。
		 * @throws RingBufferIndexException 指定された長さが範囲外の場合
		 */
		public RingBuffer setLength(int len) {
			if (len > size || len < 0)
				throw new RingBufferIndexException(len, size);
			if (this.len < len) {
				while (this.len < len) {
					this.addLast(0);
				}
			} else {
				this.len = len;
				tail = mod(head + len, size);
			}
			return this;
		}

		/**
		 * 現在のバッファの長さを開始インデックスと終了インデックスを指定して変更します。 長さが増加する場合、新しい位置には0が挿入されます。
		 *
		 * @param startIndex 開始インデックス（0 <= startIndex < sizeを満たす必要があります）（これを含む）
		 * @param endIndex   終了インデックス（0 <= endIndex <= sizeを満たす必要があります）（これを含まない）
		 * @return このインスタンス自体を返します。
		 * @throws RingBufferIndexException 指定されたインデックスが範囲外の場合 startIndex > endIndexの場合
		 */
		public RingBuffer setLength(int startIndex, int endIndex) {
			if (startIndex > endIndex)
				throw new RingBufferIndexException("Invalid range: [" + startIndex + ", " + endIndex + "]");
			if (startIndex < 0 || size <= startIndex)
				throw new RingBufferIndexException(startIndex, 0, size - 1);
			if (endIndex < 0 || size < endIndex)
				throw new RingBufferIndexException(endIndex, 0, size - 1);
			if (startIndex == endIndex) {
				clear();
				return this;
			}
			while (!isFull() && endIndex > mod(tail - head, size)) {
				addLast(0);
			}
			head = mod(startIndex + head, size);
			tail = mod(head + endIndex, size);
			len = endIndex - startIndex;
			return this;
		}

		/**
		 * 指定した要素がバッファに含まれているかを調べます。
		 *
		 * @param e 検索対象の要素
		 * @return 指定した要素が含まれている場合はtrue、含まれていない場合はfalse
		 */
		public boolean contains(int e) {
			for (int i = 0; i < len; i++) {
				if (get(i) == e)
					return true;
			}
			return false;
		}

		/**
		 * 指定した位置に要素を挿入します。 挿入により要素が移動するため、計算コストが発生します。
		 *
		 * @param index 挿入位置のインデックス。負の値は末尾からの相対位置を表します（-len <= index <= len）。
		 * @param e     挿入する要素
		 * @return このインスタンス自体を返します。
		 * @throws RingBufferIndexException バッファが満杯の場合、 またはインデックスが有効範囲外の場合
		 */
		public RingBuffer insert(int index, int e) {
			if (len == size)
				throw new RingBufferIndexException("Buffer is full");
			if (index > len || index < -len)
				throw new RingBufferIndexException(index, -len, len);
			if (index == 0) {
				addFirst(e);
			} else if (index == len) {
				addLast(e);
			} else {
				if (index < 0)
					index += len;
				if (index < len / 2) {
					addFirst(get(0));
					for (int i = 1; i < index; i++) {
						set(i, get(i + 1));
					}
					set(index, e);
				} else {
					for (int i = len; i > index; i--) {
						set(i, get(i - 1));
					}
					set(index, e);
				}
			}
			return this;
		}

		/**
		 * 指定した位置の要素を削除し、バッファ内の他の要素をシフトします。
		 *
		 * @param index 削除する要素のインデックス。負の値は末尾からの相対位置を表します（-len <= index < len）。
		 * @return このインスタンス自体を返します。
		 * @throws RingBufferIndexException バッファが空の場合 またはインデックスが有効範囲外の場合
		 */
		public RingBuffer remove(int index) {
			if (isEmpty())
				throw new RingBufferIndexException("Buffer is empty");
			if (index >= len || index < -len)
				throw new RingBufferIndexException(index, -len, len - 1);
			if (index < 0)
				index += len;
			for (int i = index; i < len - 1; i++) {
				set(i, get(i + 1));
			}
			pollLast();
			return this;
		}

		/**
		 * バッファが空かどうかを返します。
		 *
		 * @return 現在の要素数が0の場合はtrue、それ以外の場合はfalse
		 */
		public boolean isEmpty() {
			return len == 0;
		}

		/**
		 * バッファが満杯かどうかを返します。
		 *
		 * @return 現在の要素数がバッファの最大サイズに達している場合はtrue、それ以外の場合はfalse
		 */
		public boolean isFull() {
			return len == size;
		}

		/**
		 * 現在のバッファ内の要素数を返します。
		 *
		 * @return 現在のバッファ内の要素数（0以上size以下）
		 */
		public int length() {
			return len;
		}

		/**
		 * バッファの最大サイズを返します。
		 *
		 * @return バッファの最大サイズ
		 */
		public int size() {
			return size;
		}

		/**
		 * 指定された関数を使用してバッファ内の全要素を初期化します。
		 *
		 * @param generator 要素を生成する関数。インデックス（0からsize-1まで）を引数として受け取り、初期化する値を返します。
		 * @return このインスタンス自体を返します。
		 */
		public RingBuffer setAll(IntFunction<Integer> generator) {
			head = tail = 0;
			len = size;
			Arrays.setAll(buf, i -> generator.apply(i));
			return this;
		}

		/**
		 * 指定された値でバッファ全体を初期化します。
		 *
		 * @param e バッファの全ての要素を埋める値
		 * @return このインスタンス自体を返します。
		 */
		public RingBuffer fill(int e) {
			Arrays.fill(buf, e);
			return this;
		}

		/**
		 * バッファ内の全ての要素を削除し、空の状態にします。
		 *
		 * @return このインスタンス
		 */
		public RingBuffer clear() {
			head = tail = len = 0;
			return this;
		}

		/**
		 * aをbで割った余りを計算します。負の値にも対応しています。
		 *
		 * @param a 割られる数
		 * @param b 割る数（0ではない必要があります）
		 * @return aをbで割った余り。常に0以上b未満の値を返します。
		 */
		private int mod(int a, int b) {
			return (a % b + b) % b;
		}

		/**
		 * このRingBufferインスタンスのクローンを作成します。 クローンされたインスタンスは元のインスタンスの独立したコピーです。
		 *
		 * @return クローンされたRingBufferインスタンス
		 **/
		public RingBuffer clone() {
			RingBuffer rb = new RingBuffer(size);
			System.arraycopy(buf, 0, rb.buf, 0, size);
			rb.head = head;
			rb.tail = tail;
			rb.len = len;
			return rb;
		}

		/**
		 * 指定されたオブジェクトがこのRingBufferと等しいかを判定します。
		 *
		 * @param o 比較対象のオブジェクト
		 * @return trueの場合、指定されたオブジェクトがRingBufferのインスタンスであり、
		 *         バッファ内の要素と順序が完全に一致していることを示します。
		 */
		public boolean equals(Object o) {
			if (!(o instanceof RingBuffer))
				return false;
			RingBuffer other = (RingBuffer) o;
			return len == other.len && IntStream.range(0, len).allMatch(i -> get(i) == other.get(i));
		}

		/**
		 * バッファ内の要素をスペースで区切った文字列として返します。
		 *
		 * @return バッファ内の要素を表す文字列。バッファが空の場合は空文字列
		 */
		public String toString() {
			if (len == 0)
				return "";
			StringBuilder sb = new StringBuilder();
			sb.append(get(0));
			for (int i = 1; i < len; i++) {
				sb.append(" ").append(get(i));
			}
			return sb.toString();
		}

		/**
		 * RingBufferに関連する例外クラス。 主にインデックスや長さの不正使用時にスローされます。
		 */
		private class RingBufferIndexException extends RuntimeException {

			private static final long serialVersionUID = -7627324668888567160L;

			/**
			 * 指定されたエラーメッセージを使用して例外を初期化します。
			 *
			 * @param message エラーメッセージ
			 */
			public RingBufferIndexException(String message) {
				super(message);
			}

			/**
			 * 指定されたインデックスが有効範囲外である場合の例外を初期化します。
			 *
			 * @param index 不正なインデックス
			 * @param from  有効範囲の下限（含む）
			 * @param to    有効範囲の上限（含む）
			 */
			public RingBufferIndexException(int index, int from, int to) {
				super(String.format("Invalid index %d. Valid length is [%d, %d].", index, from, to));
			}

			/**
			 * 指定のlenが0 <= len <= sizeを満たさないときのエラーです。
			 *
			 * @param len  不正な長さ
			 * @param size 有効なサイズの上限
			 */
			public RingBufferIndexException(int len, int size) {
				super(String.format("Invalid length %d. Max allowed: %d.", len, size));
			}
		}
	}

	@SuppressWarnings("unused")
	private static class MathFn {

		/**
		 * a / b以下で最大の長整数を返します。
		 *
		 * @param a 割られる値(long)
		 * @param b 割る値(long)
		 * @return ⌊a / b⌋
		 */
		public static long floorLong(long a, long b) {
			return a < 0 ? (a - b + 1) / b : a / b;
		}

		/**
		 * a / b以下で最大の整数を返します。
		 *
		 * @param a 割られる値(int)
		 * @param b 割る値(int)
		 * @return ⌊a / b⌋
		 */
		public static int floorInt(int a, int b) {
			return a < 0 ? (a - b + 1) / b : a / b;
		}

		/**
		 * a / b以上で最大の長整数を返します。
		 *
		 * @param a 割られる値(long)
		 * @param b 割る値(long)
		 * @return ⌈a / b⌉
		 */
		public static long ceilLong(long a, long b) {
			return a < 0 ? a / b : (a + b - 1) / b;
		}

		/**
		 * a / b以上で最大の整数を返します。
		 *
		 * @param a 割られる値(int)
		 * @param b 割る値(int)
		 * @return ⌈a / b⌉
		 */
		public static long ceilInt(int a, int b) {
			return a < 0 ? a / b : (a + b - 1) / b;
		}

		/**
		 * doubleの高速なフォーマット。小数点第n - 1位を四捨五入します。
		 *
		 * @param x フォーマットする対象
		 * @param n 少数点以下の桁数
		 * @return String
		 */
		public static String formatDouble(double x, int n) {
			StringBuilder sb = new StringBuilder();
			if (n == 0) return sb.append(round(x)).toString();
			if (x < 0) {
				sb.append("-");
				x = -x;
			}
			x += pow(10, -n) / 2;
			sb.append((long) x).append(".");
			x -= (long) x;
			while (n-- > 0) {
				x *= 10;
				sb.append((int) x);
				x -= (int) x;
			}
			return sb.toString();
		}

		/**
		 * a ^ b % mod を求めます。
		 *
		 * @param a   底
		 * @param b   指数
		 * @param mod 割る値(素数)
		 * @return a ^ b % mod
		 */
		public static double modPow(long a, long b, long mod) {
			long ans = 1;
			boolean f = b < 0;
			if (f) b = -b;
			b %= mod - 1;
			for (; b > 0; a = a * a % mod, b >>= 1) {
				if ((b & 1) == 1)
					ans = ans * a % mod;
			}
			return f ? (double) 1 / ans : ans;
		}

		/**
		 * aのb乗を求めます
		 *
		 * @param a 底
		 * @param b 指数
		 * @return a ^ b
		 */
		public static double pow(double a, long b) {
			double ans = 1;
			boolean f = b < 0;
			if (f) b = -b;
			for (; b > 0; a *= a, b >>= 1) {
				if ((b & 1) == 1)
					ans *= a;
			}
			return f ? (double) 1 / ans : ans;
		}

		/**
		 * nが20以下の階乗を返します。
		 *
		 * @param n int
		 * @return n!
		 */
		public static long factorial_max20(int n) {
			long[] SmallFactorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
					39916800, 479001600, 6227020800L, 87178291200L, 1307674368000L,
					20922789888000L, 355687428096000L, 6402373705728000L,
					121645100408832000L, 2432902008176640000L};
			return SmallFactorials[n];
		}

		/**
		 * nの階乗をmodで割った余りを計算します。
		 *
		 * @param n int
		 * @param mod long
		 * @return n! % mod
		 */
		public static long modFactorial(int n, long mod) {
			if (n <= 20) return factorial_max20(n) % mod;
			if (n >= mod) return 0;
			if (n == mod - 1) return n;
			int twoExponent = n - Integer.bitCount(n);
			long[] oddPart = new long[(n >> 1) + 1];
			oddPart[0] = 1;
			for (int i = 3; i <= n; i += 2) {
				int idx = i >> 1;
				oddPart[idx] = oddPart[idx - 1] * i % mod;
			}
			long ans = oddPart[(n - 1) >> 1];
			for (int i = 1; n >> i > 1; i++) {
				int k = n;
				if ((k >>= i) % 2 == 1) {
					ans = ans * oddPart[k >> 1] % mod;
				} else {
					ans = ans * oddPart[(k - 1) >> 1] % mod;
				}
			}
			long twoExp = (1L << 62) % mod;
			while (twoExponent > 62) {
				ans = ans * twoExp % mod;
				twoExponent -= 62;
			}
			return ans * ((1L << twoExponent) % mod) % mod;
		}

		/**
		 * 平方数かどうかの判定
		 *
		 * @param s 判定する対象
		 * @return boolean
		 */
		public static boolean isSquareNum(long s) {
			long sqrt = round(sqrt(s));
			return s == sqrt * sqrt;
		}

		/**
		 * 立方数かどうかの判定
		 *
		 * @param c 判定する対象
		 * @return boolean
		 */
		public static boolean isCubicNum(long c) {
			long cbrt = round(cbrt(c));
			return c == cbrt * cbrt * cbrt;
		}

		/**
		 * nCrを求めます。
		 *
		 * @param n 二項係数を求めるのに用いる値
		 * @param r 二項係数を求めるのに用いる値
		 * @return nCr
		 */
		public static long comb(long n, long r) {
			if (n < 0 || r < 0) return 0;
			long ans = 1;
			r = min(n - r, r);
			for (int i = 1; i <= r; i++) {
				ans *= n - i;
				ans /= i + 1;
			}
			return ans;
		}

		/**
		 * nCrをmodで割った余りを求めます。
		 *
		 * @param n 二項係数を求めるのに用いる値
		 * @param r 二項係数を求めるのに用いる値
		 * @param mod 法とする整数
		 * @return nCr % mod
		 */
		public static long modComb(long n, long r, long mod) {
			if (n < 0 || r < 0) return 0;
			long ans = 1;
			r = min(n - r, r);
			for (int i = 0; i < r; i++) {
				ans = ans * (n - i) % mod;
				ans = ans * (long) modPow(i + 1, mod - 2, mod) % mod;
			}
			return ans;
		}

		public static long isCrossed(int Ax1, int Ay1, int Ax2, int Ay2, int Bx1, int By1, int Bx2, int By2) {
			return 1;
		}

		/**
		 * 最小公倍数を求めます
		 *
		 * @param x long
		 * @param y long
		 * @return x * (y / GCD(x, y))
		 */
		public static long LCM(long x, long y) {
			return x == 0 || y == 0 ? 0 : x * (y / GCD(x, y));
		}

		/**
		 * 最大公約数を求めます
		 *
		 * @param x long
		 * @param y long
		 * @return GCD(x, y)
		 */
		public static long GCD(long x, long y) {
			return y > 0 ? GCD(y, x % y) : x;
		}

		/**
		 * ax + by = GCD(x, y)となるx, yの組を見つけます。
		 *
		 * @param a long
		 * @param b long
		 * @param x AtomicLong
		 * @param y AtomicLong
		 * @return |x| + |y|の最小値
		 */
		public static long exGCD(long a, long b, AtomicLong x, AtomicLong y) {
			if (b == 0) {
				x.set(1);
				y.set(0);
				return a;
			}
			AtomicLong xx = new AtomicLong(), yy = new AtomicLong();
			long d = exGCD(b, a % b, yy, xx);
			y.set(yy.get() - (a / b) * xx.get());
			x.set(xx.get());
			return d;
		}

		/**
		 * オイラーのトーシェント関数に基づき1からnまでのnと互いに素な数字の個数を調べます。
		 *
		 * @param n long
		 * @return long
		 */
		public static long EulerTotientFunction(long n) {
			long sum = 1;
			for (int i = 2; i <= 3; i++) {
				long temp = 1;
				while (n % i == 0) {
					n /= i;
					temp *= i;
				}
				sum *= temp - temp / i;
			}
			for (int i = 5; (long) i * i <= n; i += 6) {
				for (int j = i; j <= i + 2; j += 2) {
					if (n % j == 0) {
						long temp = 1;
						while (n % j == 0) {
							n /= j;
							temp *= j;
						}
						sum *= temp - temp / j;
					}
				}
			}
			return n == 1 ? sum : sum * (n - 1);
		}

	}

	/**
	 * UnionFind 総グループ数、各グループの総辺数、頂点数を保持します。
	 */
	@SuppressWarnings("unused")
	private static class UnionFind {
		private int cnt;
		private final List<List<Integer>> groups;
		private final int[] root, rank, size, path;

		public UnionFind(int n) {
			cnt = n;
			root = new int[n];
			rank = new int[n];
			size = new int[n];
			path = new int[n];
			groups = new ArrayList<>(n);
			for (int i = 0; i < n; i++) {
				size[i] = 1;
				root[i] = i;
				groups.add(new ArrayList<>());
			}
		}

		/**
		 * 引数の頂点の代表元を取得します。
		 *
		 * @param x 頂点
		 * @return 頂点xの代表元
		 */
		public int find(int x) {
			return x != root[x] ? root[x] = find(root[x]) : root[x];
		}

		/**
		 * 引数の二つの頂点が同じグループに属するかどうか。
		 *
		 * @param x 頂点1
		 * @param y 頂点2
		 * @return 同じグループに属するならtrue、そうでなければfalse
		 */
		public boolean isConnected(int x, int y) {
			return find(x) == find(y);
		}

		/**
		 * 引数の二つの頂点を連結する。
		 *
		 * @param x 頂点1
		 * @param y 頂点2
		 * @return すでに連結済みならfalse、そうでなければfalse
		 */
		public boolean union(int x, int y) {
			x = find(x);
			y = find(y);
			path[x]++;
			if (x == y) return false;
			if (rank[x] < rank[y]) {
				int temp = x;
				x = y;
				y = temp;
			}
			if (rank[x] == rank[y]) rank[x]++;
			root[y] = x;
			path[x] += path[y];
			size[x] += size[y];
			cnt--;
			return true;
		}

		/**
		 * このUnionFindのグループ数を返します。
		 *
		 * @return グループ数
		 */
		public int groupCount() {
			return cnt;
		}

		/**
		 * 引数の頂点が属するグループの総辺数を返します。
		 *
		 * @param x 頂点
		 * @return グループの総辺数
		 */
		public int pathCount(int x) {
			return path[find(x)];
		}

		/**
		 * 引数の頂点の属するグループの頂点数を返します。
		 *
		 * @param x 頂点数
		 * @return グループの頂点数
		 */
		public int size(int x) {
			return size[find(x)];
		}

		/**
		 * 頂点i(0 <= i < n)を代表元とする、グループのリストを返します。 iが代表元でないとき、要素を含みません
		 *
		 * @return 全てのグループ
		 */
		public List<List<Integer>> groups() {
			for (int i = 0; i < root.length; i++) {
				groups.get(find(i)).add(i);
			}
			return groups;
		}
	}

	/**
	 * 整数と長整数に対して通常の二分探索、上限探索(Upper Bound)、下限探索(Lower Bound)を行うための抽象クラスです。
	 * 探索に失敗した際の戻り値は-(挿入位置(境界値) - 1)となっています。
	 */
	@SuppressWarnings("unused")
	private static abstract class AbstractBinarySearch {

		/**
		 * 整数範囲での通常の二分探索を行います。comparatorが0を返した時点で探索を終了します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return int
		 */
		public final int normalSearch(int l, int r) {
			return binarySearch(l, r, SearchType.NORMAL);
		}

		/**
		 * 長整数範囲での通常の二分探索を行います。comparatorが0を返した時点で探索を終了します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return long
		 */
		public final long normalSearch(long l, long r) {
			return binarySearch(l, r, SearchType.NORMAL);
		}

		/**
		 * 整数範囲での上限探索(Upper Bound)を行います。 目的の条件にちょうど当てはまる際にcomparatorが0を返すことが好ましい。
		 * comparatorが0を返した際、その値を記憶します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return 条件にちょうど当てはまる整数。もしくは上限値+1(挿入位置)。
		 */
		public final int upperBoundSearch(int l, int r) {
			return binarySearch(l, r, SearchType.UPPER_BOUND);
		}

		/**
		 * 長整数範囲での上限探索(Upper Bound)を行います。 目的の条件にちょうど当てはまる際にcomparatorが0を返すことが好ましい。
		 * comparatorが0を返した際、その値を記憶します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return 条件にちょうど当てはまる長整数。もしくは上限値+1(挿入位置)。
		 */
		public final long upperBoundSearch(long l, long r) {
			return binarySearch(l, r, SearchType.UPPER_BOUND);
		}

		/**
		 * 整数範囲での下限探索(Lower Bound)を行います。 目的の条件にちょうど当てはまる際にcomparatorが0を返すことが好ましい。
		 * comparatorが0を返した際、その値を記憶します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return 条件にちょうど当てはまる整数。もしくは下限値-1(挿入位置)。
		 */
		public final int lowerBoundSearch(int l, int r) {
			return binarySearch(l, r, SearchType.LOWER_BOUND);
		}

		/**
		 * 長整数範囲での下限探索(Lower Bound)を行います。 目的の条件にちょうど当てはまる際にcomparatorが0を返すことが好ましい。
		 * comparatorが0を返した際、その値を記憶します。
		 *
		 * @param l 下限値 (この数を含む)
		 * @param r 上限値 (この数を含む)
		 * @return 条件にちょうど当てはまる長整数。もしくは下限値-1(挿入位置)。
		 */
		public final long lowerBoundSearch(long l, long r) {
			return binarySearch(l, r, SearchType.LOWER_BOUND);
		}

		/**
		 * 内部的に利用される探索種別を示す列挙型
		 */
		private enum SearchType {
			NORMAL, UPPER_BOUND, LOWER_BOUND
		}

		/**
		 * 整数範囲での汎用二分探索メソッド
		 */
		private final int binarySearch(int l, int r, SearchType type) {
			Integer k = null;
			while (l <= r) {
				int m = (l + r) >> 1;
				switch (comparator(m)) {
					case 1:
						r = m - 1;
						break;
					case 0:
						switch (type) {
							case UPPER_BOUND:
								l = m + 1;
								break;
							case LOWER_BOUND:
								r = m - 1;
								break;
							case NORMAL:
								return m;
						}
						k = m;
						break;
					case -1:
						l = m + 1;
						break;
				}
			}
			return k != null ? k : ~l;
		}

		/**
		 * 長整数範囲での汎用二分探索メソッド
		 */
		private final long binarySearch(long l, long r, SearchType type) {
			Long k = null;
			while (l <= r) {
				long m = (l + r) >> 1L;
				switch (comparator(m)) {
					case 1:
						r = m - 1;
						break;
					case 0:
						switch (type) {
							case UPPER_BOUND:
								l = m + 1;
								break;
							case LOWER_BOUND:
								r = m - 1;
								break;
							case NORMAL:
								return m;
						}
						k = m;
						break;
					case -1:
						l = m + 1;
						break;
				}
			}
			return k != null ? k : ~l;
		}

		/**
		 * 問題に応じた実装を必要とします。条件を超過する際は1, ちょうど合致する際は0、そうでない場合は-1を返すことが望ましい。
		 */
		abstract protected int comparator(long n);
	}

	/**
	 * 標準入力を高速に処理するためのクラスです。配列の入力時に総和、最大値、最小値を取得できます。
	 */
	@SuppressWarnings("unused")
	private static final class FastScanner {
		private static final BufferedInputStream reader = new BufferedInputStream(System.in);
		private static final byte[] buf = new byte[1 << 17];
		private static int pos = 0, cnt = 0;
		private long sum, low, high;

		/**
		 * バッファから1バイトを読み込みます。
		 *
		 * @return 読み込んだバイト（byte）
		 */
		private byte read() {
			if (pos == cnt) {
				try {
					cnt = reader.read(buf, pos = 0, 1 << 17);
				} catch (IOException ignored) {
				}
			}
			if (cnt < 0)
				return 0;
			return buf[pos++];
		}

		/**
		 * 次の一文字を読み込みます。
		 *
		 * @return 読み込んだ文字(char)
		 */
		public char nextChar() {
			byte b = read();
			while (b < '!' || '~' < b)
				b = read();
			return (char) b;
		}

		/**
		 * 次のトークンを文字列(String)として読み込みます。
		 *
		 * @return 読み込んだ文字列(String)
		 */
		public String next() {
			return nextSb().toString();
		}

		/**
		 * 次のトークンを文字列(StringBuilder)として読み込みます。
		 *
		 * @return 読み込んだ文字列(StringBuilder)
		 */
		public StringBuilder nextSb() {
			StringBuilder sb = new StringBuilder();
			int b = read();
			while (b < '!' || '~' < b)
				b = read();
			while ('!' <= b && b <= '~') {
				sb.appendCodePoint(b);
				b = read();
			}
			return sb;
		}

		/**
		 * 改行までの一行を読み込みます。
		 *
		 * @return 読み込んだ行(String)
		 */
		public String nextLine() {
			StringBuilder sb = new StringBuilder();
			int b = read();
			while (b != 0 && b != '\r' && b != '\n') {
				sb.appendCodePoint(b);
				b = read();
			}
			if (b == '\r')
				read();
			return sb.toString();
		}

		/**
		 * 次の整数を読み込みます。
		 *
		 * @return 読み込んだ整数(int)
		 */
		public int nextInt() {
			int b = nextChar();
			boolean neg = b == '-';
			if (neg)
				b = read();
			int n = 0;
			while ('0' <= b && b <= '9') {
				n = n * 10 + b - '0';
				b = read();
			}
			return neg ? -n : n;
		}

		/**
		 * 次の長整数を読み込みます。
		 *
		 * @return 読み込んだ長整数(long)
		 */
		public long nextLong() {
			int b = nextChar();
			boolean neg = b == '-';
			if (neg)
				b = read();
			long n = 0;
			while ('0' <= b && b <= '9') {
				n = n * 10 + b - '0';
				b = read();
			}
			return neg ? -n : n;
		}

		/**
		 * 基数を指定して整数を読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだ整数(int)
		 */
		public int nextIntRadix(int radix) {
			return Integer.parseInt(next(), radix);
		}

		/**
		 * 基数を指定して長整数を読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだ長整数(long)
		 */
		public long nextLongRadix(int radix) {
			return Long.parseLong(next(), radix);
		}

		/**
		 * 次のトークンをBigIntegerとして読み込みます。
		 *
		 * @return 読み込んだBigInteger
		 */
		public BigInteger nextBigInteger() {
			return new BigInteger(next());
		}

		/**
		 * 基数を指定してBigIntegerを読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだBigInteger
		 */
		public BigInteger nextBigInteger(int radix) {
			return new BigInteger(next(), radix);
		}

		/**
		 * 次のトークンを浮動小数点数として読み込みます。
		 *
		 * @return 読み込んだ浮動小数点数(double)
		 */
		public double nextDouble() {
			return Double.parseDouble(next());
		}

		/**
		 * 指定された長さの文字列配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ文字列配列(String[])
		 */
		public String[] nextStrings(int n) {
			String[] s = new String[n];
			setAll(s, x -> next());
			return s;
		}

		/**
		 * 指定された長さの文字列配列を読み込み、ソートされた文字列配列として返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた文字列配列(String[])
		 */
		public String[] nextSortedStrings(int n) {
			String[] s = nextStrings(n);
			sort(s);
			return s;
		}

		/**
		 * 指定された行数・列数の二次元文字列配列を読み込みます。
		 *
		 * @param n 行数
		 * @param m 列数
		 * @return 読み込んだ二次元文字列配列(String[][])
		 */
		public String[][] nextStringMat(int n, int m) {
			String[][] s = new String[n][m];
			setAll(s, x -> nextStrings(m));
			return s;
		}

		/**
		 * 次の文字列のi番目の文字を読み込みます。
		 *
		 * @param i 読み込む文字のindex
		 * @return 読み込んだ文字(char)
		 */
		public char nextCharAt(int i) {
			return next().charAt(i);
		}

		/**
		 * 文字列を文字配列として読み込みます。
		 *
		 * @return 読み込んだ文字配列(char[])
		 */
		public char[] nextChars() {
			return next().toCharArray();
		}

		/**
		 * 指定された長さの文字配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ文字配列(char[])
		 */
		public char[] nextChars(int n) {
			char[] c = new char[n];
			for (int i = 0; i < n; i++)
				c[i] = nextChar();
			return c;
		}

		/**
		 * 文字列を読み込み、ソートされた文字配列として返します。
		 *
		 * @return ソートされた文字配列(char[])
		 */
		public char[] nextSortedChars() {
			char[] c = nextChars();
			sort(c);
			return c;
		}

		/**
		 * 指定された長さの文字配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた文字配列(char[])
		 */
		public char[] nextSortedChars(int n) {
			char[] c = nextChars(n);
			sort(c);
			return c;
		}

		/**
		 * 複数の文字列を二次元の文字配列として読み込みます。
		 *
		 * @param n 行数（文字列の個数）
		 * @return 読み込んだ二次元文字配列(char[][])
		 */
		public char[][] nextCharMat(int n) {
			char[][] c = new char[n][];
			setAll(c, x -> nextChars());
			return c;
		}

		/**
		 * 指定された行数・列数の二次元文字配列を読み込みます。
		 *
		 * @param n 行数
		 * @param m 列数
		 * @return 読み込んだ二次元文字配列(char[][])
		 */
		public char[][] nextCharMat(int n, int m) {
			char[][] c = new char[n][m];
			setAll(c, x -> nextChars(m));
			return c;
		}

		/**
		 * 指定された長さの整数(int)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ整数配列(int[])
		 */
		public int[] nextInt(int n) {
			int[] a = new int[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextInt());
			return a;
		}

		/**
		 * 指定された長さの整数(Integer)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ整数配列(Integer[])
		 */
		public Integer[] nextInts(int n) {
			Integer[] a = new Integer[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextInt());
			return a;
		}

		/**
		 * 指定された長さの整数(int)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた整数配列(int[])
		 */
		public int[] nextSortedInt(int n) {
			int[] a = nextInt(n);
			sort(a);
			return a;
		}

		/**
		 * 指定された長さの整数(Integer)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた整数配列(Integer[])
		 */
		public Integer[] nextSortedInts(int n) {
			Integer[] a = nextInts(n);
			sort(a);
			return a;
		}

		/**
		 * 整数の累積和配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 累積和配列(int[])
		 */
		public int[] nextIntSum(int n) {
			int[] a = new int[n];
			resetStats();
			updateStats(a[0] = nextInt());
			for (int i = 1; i < n; i++) {
				updateStats(a[i] = nextInt());
				a[i] += a[i - 1];
			}
			return a;
		}

		/**
		 * 二次元整数配列を読み込みます。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 読み込んだ二次元整数配列(int[][])
		 */
		public int[][] nextIntMat(int h, int w) {
			int[][] a = new int[h][w];
			setAll(a, x -> nextInt(w));
			return a;
		}

		/**
		 * 二次元整数配列を読み込み、累積和配列として返します。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 二次元累積和配列(int[][])
		 */
		public int[][] nextIntMatSum(int h, int w) {
			int[][] a = new int[h + 1][w + 1];
			for (int i = 1; i <= h; i++)
				for (int j = 1; j <= w; j++)
					a[i][j] = nextInt() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			return a;
		}

		/**
		 * 三次元整数配列を読み込みます。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 読み込んだ三次元整数配列(int[][][])
		 */
		public int[][][] nextInt3D(int x, int y, int z) {
			int[][][] a = new int[x][y][z];
			setAll(a, b -> nextIntMat(y, z));
			return a;
		}

		/**
		 * 三次元整数配列を読み込み、累積和配列として返します。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 三次元累積和配列(int[][][])
		 */
		public int[][][] nextIntSum3D(int x, int y, int z) {
			int[][][] e = new int[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++)
					for (int c = 1; c <= z; c++)
						e[a][b][c] = nextInt() + e[a - 1][b][c] + e[a][b - 1][c] + e[a][b][c - 1] - e[a - 1][b - 1][c]
								- e[a - 1][b][c - 1] - e[a][b - 1][c - 1] + e[a - 1][b - 1][c - 1];
			return e;
		}

		/**
		 * 指定された長さの長整数(long)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ長整数配列(long[])
		 */
		public long[] nextLong(int n) {
			long[] a = new long[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextLong());
			return a;
		}

		/**
		 * 指定された長さの長整数(Long)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ長整数配列(Long[])
		 */
		public Long[] nextLongs(int n) {
			Long[] a = new Long[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextLong());
			return a;
		}

		/**
		 * 指定された長さの長整数(long)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた長整数配列(long[])
		 */
		public long[] nextSortedLong(int n) {
			long[] a = nextLong(n);
			sort(a);
			return a;
		}

		/**
		 * 指定された長さの長整数(Long)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた長整数配列(Long[])
		 */
		public Long[] nextSortedLongs(int n) {
			Long[] a = nextLongs(n);
			sort(a);
			return a;
		}

		/**
		 * 長整数の累積和配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 累積和配列(long[])
		 */
		public long[] nextLongSum(int n) {
			long[] a = new long[n];
			low = high = sum = a[0] = nextLong();
			for (int i = 1; i < n; i++) {
				updateStats(a[i] = nextLong());
				a[i] += a[i - 1];
			}
			return a;
		}

		/**
		 * 二次元長整数配列を読み込みます。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 読み込んだ二次元長整数配列(long[])
		 */
		public long[][] nextLongMat(int h, int w) {
			long[][] a = new long[h][w];
			setAll(a, x -> nextLong(w));
			return a;
		}

		/**
		 * 二次元長整数配列を読み込み、累積和配列として返します。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 二次元累積和配列(long[][])
		 */
		public long[][] nextLongMatSum(int h, int w) {
			long[][] a = new long[h + 1][w + 1];
			for (int i = 1; i <= h; i++)
				for (int j = 1; j <= w; j++)
					a[i][j] = nextLong() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			return a;
		}

		/**
		 * 三次元長整数配列を読み込みます。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 読み込んだ三次元長整数配列(long[][])
		 */
		public long[][][] nextLong3D(int x, int y, int z) {
			long[][][] a = new long[x][y][z];
			setAll(a, b -> nextLongMat(y, z));
			return a;
		}

		/**
		 * 三次元長整数配列を読み込み、累積和配列として返します。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 三次元累積和配列(long[][][])
		 */
		public long[][][] nextLongSum3D(int x, int y, int z) {
			long[][][] e = new long[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++)
					for (int c = 1; c <= z; c++)
						e[a][b][c] = nextLong() + e[a - 1][b][c] + e[a][b - 1][c] + e[a][b][c - 1] - e[a - 1][b - 1][c]
								- e[a - 1][b][c - 1] - e[a][b - 1][c - 1] + e[a - 1][b - 1][c - 1];
			return e;
		}

		/**
		 * 整数を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Integer>> T nextIntCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				int a = nextInt();
				c.add(a);
				updateStats(a);
			}
			return c;
		}

		/**
		 * 指定された長さの整数のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Integer> nextIntAL(int n) {
			return nextIntCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの整数のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Integer> nextIntLL(int n) {
			return nextIntCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの整数を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Integer> nextIntHS(int n) {
			return nextIntCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの整数を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Integer> nextIntLHS(int n) {
			return nextIntCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの整数を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Integer> nextIntTS(int n) {
			return nextIntCollection(n, TreeSet::new);
		}

		/**
		 * 長整数を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Long>> T nextLongCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				long a = nextLong();
				c.add(a);
				updateStats(a);
			}
			return c;
		}

		/**
		 * 指定された長さの整数のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Long> nextLongAL(int n) {
			return nextLongCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの整数のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Long> nextLongLL(int n) {
			return nextLongCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Long> nextLongHS(int n) {
			return nextLongCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Long> nextLongLHS(int n) {
			return nextLongCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Long> nextLongTS(int n) {
			return nextLongCollection(n, TreeSet::new);
		}

		/**
		 * 文字列を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<String>> T nextStringCollection(int n, Supplier<T> s) {
			T c = s.get();
			while (n-- > 0) {
				c.add(next());
			}
			return c;
		}

		/**
		 * 指定された長さの文字列のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<String> nextStringAL(int n) {
			return nextStringCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの文字列のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<String> nextStringLL(int n) {
			return nextStringCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<String> nextStringHS(int n) {
			return nextStringCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<String> nextStringLHS(int n) {
			return nextStringCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<String> nextStringTS(int n) {
			return nextStringCollection(n, TreeSet::new);
		}

		/**
		 * 文字を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Character>> T nextCharacterCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				char t = nextChar();
				c.add(t);
				updateStats(t);
			}
			return c;
		}

		/**
		 * 指定された長さの文字のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Character> nextCharacterAL(int n) {
			return nextCharacterCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの文字のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Character> nextCharacterLL(int n) {
			return nextCharacterCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの文字を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Character> nextCharacterHS(int n) {
			return nextCharacterCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの文字を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Character> nextCharacterLHS(int n) {
			return nextCharacterCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの文字を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Character> nextCharacterTS(int n) {
			return nextCharacterCollection(n, TreeSet::new);
		}

		/**
		 * 整数をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Integer, Integer>> T nextIntMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				int a = nextInt();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Integer, Integer> nextIntMultisetHM(int n) {
			return nextIntMultiset(n, HashMap::new);
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Integer, Integer> nextIntMultisetLHM(int n) {
			return nextIntMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Integer, Integer> nextIntMultisetTM(int n) {
			return nextIntMultiset(n, TreeMap::new);
		}

		/**
		 * 長整数をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Long, Integer>> T nextLongMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				long a = nextLong();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Long, Integer> nextLongMultisetHM(int n) {
			return nextLongMultiset(n, HashMap::new);
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Long, Integer> nextLongMultisetLHM(int n) {
			return nextLongMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Long, Integer> nextLongMultisetTM(int n) {
			return nextLongMultiset(n, TreeMap::new);
		}

		/**
		 * 文字列をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<String, Integer>> T nextStringMultiset(int n, Supplier<T> s) {
			T c = s.get();
			while (n-- > 0) {
				String a = next();
				c.put(a, c.getOrDefault(a, 0) + 1);
			}
			return c;
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<String, Integer> nextStringMultisetHM(int n) {
			return nextStringMultiset(n, HashMap::new);
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<String, Integer> nextStringMultisetLHM(int n) {
			return nextStringMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<String, Integer> nextStringMultisetTM(int n) {
			return nextStringMultiset(n, TreeMap::new);
		}

		/**
		 * 文字をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Character, Integer>> T nextCharMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				char a = nextChar();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Character, Integer> nextCharMultisetHM(int n) {
			return nextCharMultiset(n, HashMap::new);
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Character, Integer> nextCharacterMultisetLHM(int n) {
			return nextCharMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Character, Integer> nextCharMultisetTM(int n) {
			return nextCharMultiset(n, TreeMap::new);
		}

		/**
		 * 読み込んだ配列の最小値を返します。
		 *
		 * @return 最小値
		 */
		public long getLowestNum() {
			return low;
		}

		/**
		 * 読み込んだ配列の最大値を返します。
		 *
		 * @return 最大値
		 */
		public long getHighestNum() {
			return high;
		}

		/**
		 * 読み込んだ配列の総和を返します。
		 *
		 * @return 総和
		 */
		public long getSum() {
			return sum;
		}

		/**
		 * 統計情報をリセットします（最小値、最大値、総和）。
		 */
		private void resetStats() {
			low = Long.MAX_VALUE;
			high = Long.MIN_VALUE;
			sum = 0;
		}

		/**
		 * 読み込んだ値で統計情報（最小値、最大値、総和）を更新します。
		 *
		 * @param a 更新する値
		 */
		private void updateStats(long a) {
			sum += a;
			low = min(low, a);
			high = max(high, a);
		}
	}

	/**
	 * 標準出力を管理するクラスです。<p>
	 * デフォルトではautoFlushはfalseであり、出力内容をStringBuilderに蓄積して一括出力します。<p>
	 * - autoFlushが有効な場合、出力は即座に標準出力に書き込まれ、StringBuilderは使用されません。<p>
	 * - 内部でStringBuilderを使用しているため、スレッドセーフではありません。<p>
	 * - 大量の出力が必要な場合は、autoFlushを無効にすることを推奨します。
	 */
	@SuppressWarnings("unused")
	private static final class FastPrinter {
		private final StringBuilder sb;
		private final boolean autoFlush;
		private int capacity;

		/**
		 * デフォルトの設定でFastPrinterを初期化します。<p>
		 * バッファ容量: 65536 <p>
		 * autoFlush: false
		 */
		public FastPrinter() {
			this(65536, false);
		}

		/**
		 * 指定されたバッファ容量でFastPrinterを初期化します。<p>
		 * autoFlushはfalseに設定されます。
		 *
		 * @param capacity バッファの初期容量（文字単位）
		 */
		public FastPrinter(int capacity) {
			this(capacity, false);
		}

		/**
		 * autoFlushの設定を指定してFastPrinterを初期化します。<p>
		 * バッファ容量: 65536
		 *
		 * @param autoFlush trueの場合、出力は即座に標準出力に書き込まれます。
		 *                  falseの場合、出力はStringBuilderに蓄積されます。
		 */
		public FastPrinter(boolean autoFlush) {
			this(65536, autoFlush);
		}

		/**
		 * 指定されたバッファ容量とautoFlushの設定でFastPrinterを初期化します。
		 *
		 * @param capacity  バッファの初期容量（文字単位）
		 * @param autoFlush trueの場合、出力は即座に標準出力に書き込まれます。
		 *                  falseの場合、出力はStringBuilderに蓄積されます。
		 */
		public FastPrinter(int capacity, boolean autoFlush) {
			this.autoFlush = autoFlush;
			this.capacity = capacity;
			sb = autoFlush ? null : new StringBuilder(capacity);
		}

		/**
		 * 改行を一つ出力します。
		 */
		public FastPrinter println() {
			print("\n");
			return this;
		}

		/**
		 * 指定されたObjectを出力します（改行付き）。
		 *
		 * @param o Object
		 */
		public FastPrinter println(Object o) {
			print(o).println();
			return this;
		}

		/**
		 * 指定されたStringを出力します（改行付き）。
		 *
		 * @param s String
		 */
		public FastPrinter println(String s) {
			print(s).println();
			return this;
		}

		/**
		 * 指定されたbooleanを出力します（改行付き）。
		 *
		 * @param f boolean
		 */
		public FastPrinter println(boolean f) {
			print(f).println();
			return this;
		}

		/**
		 * 指定されたcharを出力します（改行付き）。
		 *
		 * @param c char
		 */
		public FastPrinter println(char c) {
			print(c).println();
			return this;
		}

		/**
		 * 指定されたintを出力します（改行付き）。
		 *
		 * @param a int
		 */
		public FastPrinter println(int a) {
			print(a).println();
			return this;
		}

		/**
		 * 指定されたlongを出力します（改行付き）。
		 *
		 * @param a long
		 */
		public FastPrinter println(long a) {
			print(a).println();
			return this;
		}

		/**
		 * 指定されたdoubleを出力します（改行付き）。
		 *
		 * @param a double
		 */
		public FastPrinter println(double a) {
			print(a).println();
			return this;
		}

		/**
		 * 指定された桁数でdoubleを出力します（改行付き）。<p>
		 * 出力は小数点以下n桁に丸められます。<p>
		 * 丸め処理には四捨五入を使用します。
		 *
		 * @param a double
		 * @param n int 小数点以下の桁数（0以上）
		 */
		public FastPrinter println(double a, int n) {
			print(a, n).println();
			return this;
		}

		/**
		 * 2つの整数をそれぞれ改行して出力します。
		 *
		 * @param a int
		 * @param b int
		 */
		public FastPrinter println(int a, int b) {
			println(a).println(b);
			return this;
		}

		/**
		 * 2つの整数をそれぞれ改行して出力します。
		 *
		 * @param a int
		 * @param b long
		 */
		public FastPrinter println(int a, long b) {
			println(a).println(b);
			return this;
		}

		/**
		 * 2つの整数をそれぞれ改行して出力します。
		 *
		 * @param a long
		 * @param b int
		 */
		public FastPrinter println(long a, int b) {
			println(a).println(b);
			return this;
		}

		/**
		 * 2つの整数をそれぞれ改行して出力します。
		 *
		 * @param a long
		 * @param b long
		 */
		public FastPrinter println(long a, long b) {
			println(a).println(b);
			return this;
		}

		/**
		 * 指定された配列の各要素を改行区切りで出力し、行末は改行します。
		 *
		 * @param o Object...
		 */
		public FastPrinter println(Object... o) {
			for (Object x : o)
				println(x);
			return this;
		}

		/**
		 * 指定された配列の各要素を改行区切りで出力し、行末は改行します。
		 *
		 * @param s String[]
		 */
		public FastPrinter println(String[] s) {
			for (String x : s)
				println(x);
			return this;
		}

		/**
		 * 指定された配列の各要素を改行区切りで出力し、行末は改行します。
		 *
		 * @param c char[]
		 */
		public FastPrinter println(char[] c) {
			for (char x : c)
				println(x);
			return this;
		}

		/**
		 * 指定された配列の各要素を改行区切りで出力し、行末は改行します。
		 *
		 * @param a int[]
		 */
		public FastPrinter println(int[] a) {
			for (int x : a)
				println(x);
			return this;
		}

		/**
		 * 指定された配列の各要素を改行区切りで出力し、行末は改行します。
		 *
		 * @param a long[]
		 */
		public FastPrinter println(long[] a) {
			for (long x : a)
				println(x);
			return this;
		}

		/**
		 * 指定された二次元配列を出力し、行末は改行します。<p>
		 * 各列を半角スペースで区切り、行ごとに改行します。
		 *
		 * @param o Object[][]
		 */
		public FastPrinter println(Object[][] o) {
			for (Object[] x : o)
				print(x).println();
			return this;
		}

		/**
		 * 指定された二次元配列を出力し、行末は改行します。<p>
		 * 各列を半角スペースで区切り、行ごとに改行します。
		 *
		 * @param c char[][]
		 */
		public FastPrinter println(char[][] c) {
			for (char[] x : c)
				print(x).println();
			return this;
		}

		/**
		 * 指定された二次元配列を出力し、行末は改行します。<p>
		 * 各列を半角スペースで区切り、行ごとに改行します。
		 *
		 * @param a int[][]
		 */
		public FastPrinter println(int[][] a) {
			for (int[] x : a)
				print(x).println();
			return this;
		}

		/**
		 * 指定された二次元配列を出力し、行末は改行します。<p>
		 * 各列を半角スペースで区切り、行ごとに改行します。
		 *
		 * @param a long[][]
		 */
		public FastPrinter println(long[][] a) {
			for (long[] x : a)
				print(x).println();
			return this;
		}

		/**
		 * 指定された二次元配列を出力し行末は改行します。
		 * 各列を区切り文字無しで出力し、行ごとに改行します。
		 *
		 * @param c char[][]
		 */
		public FastPrinter printChars(char[][] c) {
			for (char[] x : c)
				printChars(x).println();
			return this;
		}

		/**
		 * 指定されたObjectを出力します（改行無し）。
		 *
		 * @param o Object
		 */
		public FastPrinter print(Object o) {
			if (autoFlush) {
				System.out.print(o);
			} else {
				String str = o.toString();
				isFull(str.length());
				sb.append(str);
			}
			return this;
		}

		/**
		 * 指定されたStringを出力します（改行無し）。
		 *
		 * @param s String
		 */
		public FastPrinter print(String s) {
			if (autoFlush) {
				System.out.print(s);
			} else {
				isFull(s.length());
				sb.append(s);
			}
			return this;
		}

		/**
		 * 指定されたbooleanを出力します（改行無し）。
		 *
		 * @param f boolean
		 */
		public FastPrinter print(boolean f) {
			if (autoFlush) {
				System.out.print(f);
			} else {
				String str = f ? "true" : "false";
				isFull(str.length());
				sb.append(str);
			}
			return this;
		}

		/**
		 * 指定されたcharを出力します（改行無し）。
		 *
		 * @param c char
		 */
		public FastPrinter print(char c) {
			if (autoFlush) {
				System.out.print(c);
			} else {
				isFull(1);
				sb.append(c);
			}
			return this;
		}

		/**
		 * 指定されたintを出力します（改行無し）。
		 *
		 * @param a int
		 */
		public FastPrinter print(int a) {
			if (autoFlush) {
				System.out.print(a);
			} else {
				isFull(10);
				sb.append(a);
			}
			return this;
		}

		/**
		 * 指定されたlongを出力します（改行無し）。
		 *
		 * @param a long
		 */
		public FastPrinter print(long a) {
			if (autoFlush) {
				System.out.print(a);
			} else {
				isFull(20);
				sb.append(a);
			}
			return this;
		}

		/**
		 * 指定されたdoubleを出力します（改行無し）。
		 *
		 * @param a double
		 */
		public FastPrinter print(double a) {
			if (autoFlush) {
				System.out.print(a);
			} else {
				isFull(20);
				sb.append(a);
			}
			return this;
		}

		/**
		 * 指定された桁数でdoubleを出力します（改行無し）。<p>
		 * 出力は小数点以下n桁に丸められます。<p>
		 * 丸め処理には四捨五入を使用します。
		 *
		 * @param a double
		 * @param n int 小数点以下の桁数（0以上）
		 */
		public FastPrinter print(double a, int n) {
			if (n == 0) {
				print(Math.round(a));
				return this;
			}
			if (a < 0) {
				print("-");
				a = -a;
			}
			a += Math.pow(10, -n) / 2;
			print((long) a).print(".");
			a -= (long) a;
			while (n-- > 0) {
				a *= 10;
				print((int) a);
				a -= (int) a;
			}
			return this;
		}

		/**
		 * 2つの整数を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a int
		 * @param b int
		 */
		public FastPrinter print(int a, int b) {
			print(a).print(" ").print(b);
			return this;
		}

		/**
		 * 2つの整数を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a int
		 * @param b long
		 */
		public FastPrinter print(int a, long b) {
			print(a).print(" ").print(b);
			return this;
		}

		/**
		 * 2つの整数を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a long
		 * @param b int
		 */
		public FastPrinter print(long a, int b) {
			print(a).print(" ").print(b);
			return this;
		}

		/**
		 * 2つの整数を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a long
		 * @param b long
		 */
		public FastPrinter print(long a, long b) {
			print(a).print(" ").print(b);
			return this;
		}

		/**
		 * 指定された配列の各要素を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param o Object...
		 */
		public FastPrinter print(Object... o) {
			print(o[0]);
			for (int i = 1; i < o.length; i++) {
				print(" ").print(o[i]);
			}
			return this;
		}

		/**
		 * 指定された配列の各要素を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param s String[]
		 */
		public FastPrinter print(String[] s) {
			print(s[0]);
			for (int i = 1; i < s.length; i++) {
				print(" ").print(s[i]);
			}
			return this;
		}

		/**
		 * 指定された配列の各要素を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param c char[]
		 */
		public FastPrinter print(char[] c) {
			print(c[0]);
			for (int i = 1; i < c.length; i++) {
				print(" ").print(c[i]);
			}
			return this;
		}

		/**
		 * 指定された配列の各要素を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a int[]
		 */
		public FastPrinter print(int[] a) {
			print(a[0]);
			for (int i = 1; i < a.length; i++) {
				print(" ").print(a[i]);
			}
			return this;
		}

		/**
		 * 指定された配列の各要素を半角スペース区切りで出力し、行末は改行しません。
		 *
		 * @param a long[]
		 */
		public FastPrinter print(long[] a) {
			print(a[0]);
			for (int i = 1; i < a.length; i++) {
				print(" ").print(a[i]);
			}
			return this;
		}

		/**
		 * 指定された配列の各要素を区切り文字無しで出力し、行末は改行しません。。
		 *
		 * @param c char[]
		 */
		public FastPrinter printChars(char[] c) {
			if (autoFlush) {
				System.out.print(c);
			} else {
				isFull(c.length);
				sb.append(c);
			}
			return this;
		}

		/**
		 * フォーマットを指定して出力します。
		 *
		 * @param format String 書式文字列
		 * @param args   Object... 書式に割り当てる値
		 */
		public FastPrinter printf(String format, Object... args) {
			print(String.format(format, args));
			return this;
		}

		/**
		 * フォーマットを指定して出力します。 このとき指定した言語環境での整形を行います。
		 *
		 * @param locale Locale 言語環境
		 * @param format String 書式文字列
		 * @param args   Object... 書式に割り当てる値
		 */
		public FastPrinter printf(Locale locale, String format, Object... args) {
			print(String.format(locale, format, args));
			return this;
		}

		/**
		 * 現在のバッファに保持している出力内容を逆順に並べ替えます。
		 */
		public FastPrinter reverse() {
			sb.reverse();
			return this;
		}

		/**
		 * 現在のバッファに保持している全ての出力内容を標準出力に出力し、バッファをクリアします。
		 */
		public FastPrinter flush() {
			System.out.print(sb);
			clear();
			return this;
		}

		/**
		 * StringBuilderの初期化を行います。
		 */
		public FastPrinter clear() {
			sb.setLength(0);
			return this;
		}

		/**
		 * StringBuilderの容量を指定した値に確保します。
		 * 指定した容量が現在の容量より小さい場合、変更は行われません。
		 *
		 * @param capacity 確保する容量（文字単位）
		 */
		public FastPrinter ensureCapacity(int capacity) {
			if (this.capacity >= capacity) return this;
			this.capacity = capacity;
			sb.ensureCapacity(capacity);
			return this;
		}

		private void isFull(int length) {
			if (sb.length() + length > sb.capacity()) flush();
		}
	}

}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

class UnionFind{
  /**@param {Number} n n頂点のグラフ*/
  constructor(n){this.a=new Int32Array(n).fill(-1);}

  /**@param {Number} i 頂点i
   * @returns {Number} 頂点iの属する連結成分の代表元
   */
  root(i){
    return this.a[i]<0?i:this.a[i]=this.root(this.a[i]);
  }

  /**@param {Number} x 頂点x
   * @param {Number} y 頂点y
   * @returns 頂点x,yが連結かどうか
   */
  same(x,y){return this.root(x)===this.root(y);}

  /**辺(x,y)を足す。
   * @param {Number} x 頂点x
   * @param {Number} y 頂点y
   * @returns 辺(x,y)が非連結ならtrue
   */
  unite(x,y){
    const a=this.a;
    x=this.root(x),y=this.root(y);
    if(x===y)return false;
    if(y<x)a[y]+=a[x],a[x]=y;
    else a[x]+=a[y],a[y]=x;
    return true;
  }

  /**@param {Number} i 頂点i
   * @returns 頂点iの属する連結成分のサイズ
   */
  size(i){return -this.a[this.root(i)];}
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var [n,m] = nexts(2);
  var uf = new UnionFind(n+1);
  var ab = [];
  var cnt = n-1;
  for(var i = 0; i < m; i++){
    var [a,b] = nexts(2);
    if(uf.unite(a,b))cnt--;
    else ab.push([a,b,i+1]);
  }
  console.log(cnt);
  var rt = [];
  for(var i = 0; i < n; i++){
    if(uf.root(i+1) === i+1)rt.push(i+1);
  }
  while(cnt){
    cnt--;
    for(var i = ab.length; i--;){
      var [a,b,id] = ab[i];
      var r = rt.at(-1);
      rt.pop();
      if(uf.unite(a,r)){
        print(id+" "+b+" "+r);
      }else if(uf.unite(b,r)){
        print(id+" "+a+" "+r);
      }else{
        print(id+" "+a+" "+rt.at(-1));
        uf.unite(b,rt.at(-1));
        rt.pop();
        rt.push(r);
      }
      ab.pop();
      break;
    }
  }
}

Python solution:
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

N,M = list(map(int,input().split()))
free = []
uf = UnionFind(N)
for i in range(M):
    a,b = list(map(int,input().split()))
    a -= 1;b -= 1
    if(uf.same(a,b)):
        free.append((a,b,i))
    else:
        uf.union(a,b)

groups = uf.group_count()
print(groups-1)
looking = 0
for a,b,i in free:
    while(True):
        if(groups == 1):break
        if(not uf.same(looking,b)):
            uf.union(looking,b)
            print(i+1,a+1,looking+1)
            groups -= 1
            break
        elif(not uf.same(looking,a)):
            uf.union(looking,a)
            print(i+1,b+1,looking+1)
            groups -= 1
            break
        else:
            looking += 1
    if(groups == 1):break

Ruby solution:
def uf(i) (i > u=U[i]) ? U[i]=uf(u) : i end
P = $<.map {_1.split.map &:to_i}
N,M = P[0]
U = [*0..N]
H = U.map {{}}
1.upto(M) {|m|
  a,b = P[m]
  a,b = uf(a),uf(b)
  if a==b
    (H[a] or H[a]={})[m] = 0
  else
    a,b = b,a if a > b
    U[b] = a
    g,h = H[b],H[a]
    g,h,H[a] = h,g,g if g.size > h.size
    h.merge! g
  end
}
A,Q = [],[]
1.upto(N) {|n| uf(n) < n or Q << (H[n].keys << n)}
Q.sort_by! {_1.size}
*q,i = Q.shift
while Q[0]
  *r,j = Q.pop
  A <<  if r[0]
    m = r.pop
    q.concat r
    a,b = P[m]
    [m, a==j ? b : a, i]
  else
    if !q[0]
      Q << (r<< j) << [i]
      next (*q,i = Q.shift)
    end
    m = q.pop
    a,b = P[m]
    [m, a==i ? b : a, j]
  end
end
p A.size
A.each {puts _1*' '}