NamPE286

// https://cses.fi/problemset/result/7855807/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class BinaryLifting {
    vector<vector<ll>> graph;
    vector<vector<ll>> parent;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class MergeSortTreeImmutable {
    struct Node {
        vector<ll> v;
        pair<ll, ll> range;
        Node* left = nullptr;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DSU {
    vector<ll> p;             // parent if positive, size if negative, parent of root is the size of component
    stack<pair<ll, ll>> log;  // keep track of p[i] value history, first is index, second is value
    stack<ll> size;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DFSTree {
    vector<ll> nums, low;
    vector<bool> deleted;
    stack<ll> st;
    vector<ll> scc;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SegmentTree {
   private:
    struct Node {
        ll value;
        pair<ll, ll> range;

NamPE286

// https://cses.fi/problemset/task/1647

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SparseTable {
   private:
    vector<vector<ll>> ST;

NamPE286

// https://cses.fi/problemset/task/2195/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll crossProd(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

NamPE286

// https://cses.fi/problemset/task/1688/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class BinaryLifting {
    ll MAXLOG;
    vector<vector<ll>> parent;

NamPE286

// https://cses.fi/problemset/task/1688/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MAXLOG = 18;

void preCalc(vector<vector<ll>>& parent) {

NamPE286

// https://cses.fi/problemset/task/1687/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll jump(vector<vector<ll>>& parent, ll x, ll k) {
    for(ll i = 0; i <= 18; i++) {
        if(k & (1 << i)) {