from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, groupby
from heapq import heappop, heappush
import math, sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
def printl(li, sep=" "): print(sep.join(map(str, li)))
def yn(flag): print(Yes if flag else No)
_int = lambda x: int(x)-1
MOD = 998244353 #10**9+7
INF = 1<<60
Yes, No = "Yes", "No"

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x

import typing
class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push((right - 1) >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None) -> None:
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])

    def _push(self, k: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id

class DSU:
    '''
    Implement (union by size) + (path halving)

    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        parent = self.parent_or_size[a]
        while parent >= 0:
            if self.parent_or_size[parent] < 0:
                return parent
            self.parent_or_size[a], a, parent = (
                self.parent_or_size[parent],
                self.parent_or_size[parent],
                self.parent_or_size[self.parent_or_size[parent]]
            )

        return a

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))

class HLD:
    N: int
    E: list[list[tuple[int, int]]]
    root: int
    parent: list[int]
    depth: list[int]
    size: list[int]
    heavy: list[int]
    head: list[int]
    vid: list[int]
    inv_vid: list[int]
    dist_from_root: list[int]
    edge_to_child: list[int]

    def __init__(self, N: int, E, root: int = 0) -> None:
        """HLD (Heavy-Light Decomposition) クラスを初期化し、内部構造を構築する。

        Args:
            N (int): 木の頂点数。
            E (Union[List[Tuple], List[List]]): 木の構造を表すデータ。
                辺リスト形式 [(u, v), ...] もしくは [(u, v, w), ...]、
                または隣接リスト形式 [[v, ...], ...] もしくは [[(v, w), ...], ...]。
            root (int): 木の根とする頂点番号。デフォルトは 0。

        Note:
            Codonの静的型チェックを回避するため、辺リストの解析にはリスト変換を利用している。
        """
        self.N = N
        self.root = root
        self.E = [[] for _ in range(N)]
        self.edge_to_child = []
        
        edge_list_for_child: list[tuple[int, int]] = []
        
        if len(E) > 0:
            sample = E[0]
            if isinstance(sample, tuple):
                for e in E:
                    e_list = list(e)
                    u, v = e_list[0], e_list[1]
                    w = e_list[2] if len(e_list) >= 3 else 1
                    self.E[u].append((v, w))
                    self.E[v].append((u, w))
                    edge_list_for_child.append((u, v))
            else:
                for i in range(N):
                    for e in E[i]:
                        if isinstance(e, int):
                            v_id = e
                            w_val = 1
                        else:
                            # タプルやリストから安全に値を取る
                            e_inner = list(e)
                            v_id = e_inner[0]
                            w_val = e_inner[1]
                        self.E[i].append((v_id, w_val))
                        if i < v_id:
                            edge_list_for_child.append((i, v_id))

        self.parent = [0] * N
        self.depth = [0] * N
        self.size = [0] * N
        self.heavy = [-1] * N
        self.head = [0] * N
        self.vid = [0] * N
        self.inv_vid = []
        self.dist_from_root = [0] * N
        
        self._build()

        if len(edge_list_for_child) > 0:
            self.edge_to_child = [0] * len(edge_list_for_child)
            for i in range(len(edge_list_for_child)):
                uv = edge_list_for_child[i]
                u_id, v_id = uv[0], uv[1]
                self.edge_to_child[i] = v_id if self.depth[v_id] > self.depth[u_id] else u_id

    def _build(self) -> None:
        """木の情報を走査し、部分木サイズ、重い辺、各頂点のHLD上のIDを計算する。

        このメソッドは内部的に2回の走査を行う:
        1. BFS/スタックによる走査で親子関係、深さ、根からの距離を計算。
        2. 逆順走査で部分木サイズと重い子 (heavy child) を決定。
        その後、重い辺を優先的に走査してパスを分解 (Heavy-Light Decomposition) し、
        各頂点にセグメント木等で利用可能な連続した ID (vid) を割り当てる。
        """
        N = self.N
        E = self.E
        parent = self.parent
        depth = self.depth
        size = self.size
        dist_from_root = self.dist_from_root
        heavy = self.heavy
        q = [(-1, self.root)]
        order = []
        while q:
            p, i = q.pop()
            order.append(i)
            parent[i] = p
            size[i] = 1
            for j, w in E[i]:
                if p == j: continue
                depth[j] = depth[i]+1
                dist_from_root[j] = dist_from_root[i]+w
                q.append((i, j))
        
        for i in reversed(order):
            p = parent[i]
            if p == -1: continue
            size[p] += size[i]
            if heavy[p] == -1 or size[heavy[p]] < size[i]:
                heavy[p] = i        
        
        head = self.head
        vid = self.vid
        inv_vid = self.inv_vid
        q = [(self.root, self.root)]
        while q:
            i, hi = q.pop()
            inv_vid.append(i)
            head[i] = hi
            for j, _ in E[i]:
                if j == parent[i]: continue
                if j == heavy[i]: continue
                q.append((j, j))
            if heavy[i] >= 0:
                q.append((heavy[i], hi))
        for i in range(N):
            vid[inv_vid[i]] = i

    def get_lca(self, u: int, v: int):
        """2頂点 u, v の最近共通祖先 (LCA) を返す。

        Args:
            u (int): 頂点番号。
            v (int): 頂点番号。

        Returns:
            int: LCA となる頂点番号。
        """
        head = self.head
        depth = self.depth
        parent = self.parent
        while True:
            hu = head[u]
            hv = head[v]
            if hu == hv: break
            if depth[hu] < depth[hv]:
                v = parent[hv]
            else:
                u = parent[hu]
        lca = u if depth[u] < depth[v] else v
        return lca

    def kth_ancestor(self, u: int, k: int) -> int:
        """頂点 u から k 個上の祖先を返す。

        Args:
            u (int): 頂点番号。
            k (int): 遡る数。

        Returns:
            int: 祖先の頂点番号。存在しない場合は -1。
        """
        head = self.head
        depth = self.depth
        parent = self.parent
        target = depth[u] - k
        if target < 0: return -1
        while True:
            hu = head[u]
            if depth[hu] <= target: break
            u = parent[head[u]]
        vid = self.vid
        uid = vid[u]
        targetid = uid - (depth[u]-target)
        v = self.inv_vid[targetid]
        return v

    def jump(self, u: int, v: int, k: int) -> int:
        """u-v パス上で u から数えて k 個目の頂点を返す。

        Args:
            u (int): 始点。
            v (int): 終点。
            k (int): 移動ステップ数。

        Returns:
            int: 到達した頂点番号。パスの長さを超える場合は -1。
        """
        d = self.get_edge_dist(u, v)
        if k > d: return -1
        lca = self.get_lca(u, v)
        d_u = self.depth[u] - self.depth[lca]
        if d_u >= k:
            return self.kth_ancestor(u, k)
        else:
            return self.kth_ancestor(v, d - k)

    def get_dist(self, u: int, v: int) -> int:
        """2頂点 u, v 間の最短距離（重みの総和）を返す。

        Args:
            u (int): 頂点1。
            v (int): 頂点2。

        Returns:
            int: u-v 間の累積重み。
        """
        lca = self.get_lca(u, v)
        return self.dist_from_root[u] + self.dist_from_root[v] - 2 * self.dist_from_root[lca]

    def is_on_path(self, u: int, v: int, x: int) -> bool:
        """頂点 x がパス u-v 上に存在するか判定する。

        Args:
            u (int): パス端点1。
            v (int): パス端点2。
            x (int): 判定対象の頂点。

        Returns:
            bool: x がパス上に存在すれば True。
        """
        return self.get_edge_dist(u, x) + self.get_edge_dist(x, v) == self.get_edge_dist(u, v)


    def get_edge_dist(self, u: int, v: int) -> int:
        """2頂点間のエッジ数(重みによらない距離)を計算する。

        Args:
            u (int): 頂点1。
            v (int): 頂点2。

        Returns:
            int: u-v パスを構成するエッジの個数。
        """
        lca = self.get_lca(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[lca]
    
    def path_sections(self, u: int, v: int, edge: bool = False):
        """
        u-v パスをセグメント木上の連続区間 [l, r) に分解して yield する。
        戻り値: (l, r, is_reverse)
        
        Args:
            u, v: 端点となる頂点
            edge: True の場合、辺クエリ(LCAを含まない)として処理する
        """
        head = self.head
        depth = self.depth
        parent = self.parent
        vid = self.vid
        # u側（登り）とv側（最終的に降りになる）の区間を溜めるリスト
        # 各要素は (l, r, is_reverse)
        l_parts: list[tuple[int, int, bool]] = []
        r_parts: list[tuple[int, int, bool]] = []
        
        while head[u] != head[v]:
            if depth[head[u]] > depth[head[v]]:
                # u側を登る: IDが減る方向なので is_reverse=True
                l_parts.append((vid[head[u]], vid[u] + 1, True))
                u = parent[head[u]]
            else:
                # v側を登る: 後で逆順(降り)にするため、ここでは反転させない(False)
                r_parts.append((vid[head[v]], vid[v] + 1, False))
                v = parent[head[v]]
        
        # 同じ Chain に到達した後の、LCA付近の処理
        if depth[u] > depth[v]:
            # u側が深い場合
            l_offset = 1 if edge else 0
            # 頂点クエリなら [vid[v], vid[u]+1], 辺クエリなら [vid[v]+1, vid[u]+1]
            if vid[v] + l_offset < vid[u] + 1:
                l_parts.append((vid[v] + l_offset, vid[u] + 1, True))
        else:
            # v側が深い(または同じ)場合
            r_offset = 1 if edge else 0
            # 頂点クエリなら [vid[u], vid[v]+1], 辺クエリなら [vid[u]+1, vid[v]+1]
            if vid[u] + r_offset < vid[v] + 1:
                r_parts.append((vid[u] + r_offset, vid[v] + 1, False))
        
        # 1. u から LCA への昇順区間を順番に出す
        for section in l_parts:
            yield section
            
        # 2. v 側のリストを逆順にして、LCA から v へ降りる順序で出す
        # reversed() を使うことで、LCAに近い方の区間から順に出現する
        for section in reversed(r_parts):
            yield section
    
    def prod_path(self, u: int, v: int, e, prod_func, op, edge: bool = False):
        """u-v パス上の値を集約して返す。

        Args:
            u (int): 始点。
            v (int): 終点。
            e (T): 単位元。
            prod_func (Callable[[int, int], tuple[T, T]]): セグメント木の範囲取得関数。 (forward, backward) のペアを返す必要があります。
            op (Callable[[T, T], T]): 二項演算。
            edge (bool): True の場合、辺クエリ (LCA を含まない) として処理する。

        Returns:
            T: パス上の要素を op で集約した結果。
        """
        res = e
        for l, r, is_rev in self.path_sections(u, v, edge):
            fwd, bwd = prod_func(l, r)
            # 登りなら backward、降りなら forward を使う
            chunk = bwd if is_rev else fwd
            res = op(res, chunk)
        return res
            
    def prod_subtree(self, u: int, e, prod_func, op, edge: bool = False):
        """頂点 u の部分木を集約して返す。

        Args:
            u (int): 部分木の根となる頂点。
            e (T): 単位元。
            prod_func (Callable[[int, int], tuple[T, T]]): セグメント木の範囲取得関数。
            op (Callable[[T, T], T]): 二項演算。
            edge (bool): True の場合、辺クエリ (u 直上の辺を含まない) として処理する。

        Returns:
            T: 部分木内の要素を集約した結果。
        """
        l = self.vid[u]
        r = self.vid[u] + self.size[u]
        if edge:
            l += 1
        if l < r:
            fwd, _ = prod_func(l, r)
            return fwd
        return e
    
    def apply_path(self, u: int, v: int, x, apply_func, edge: bool = False) -> None:
        """u-v パス上の要素に一括操作 (範囲更新) を適用する。

        Args:
            u (int): 始点。
            v (int): 終点。
            x (F): 作用させる値 (作用素)。
            apply_func (Callable[[int, int, F], None]): セグメント木の範囲更新関数 (apply(l, r, x))。
            edge (bool): True の場合、辺クエリ (LCA を含まない) として処理する。
        """
        for l, r, _ in self.path_sections(u, v, edge):
            apply_func(l, r, x)
            
    def apply_subtree(self, u: int, x, apply_func, edge: bool = False) -> None:
        """頂点 u の部分木に一括操作 (範囲更新) を適用する。

        Args:
            u (int): 部分木の根となる頂点。
            x (F): 作用させる値 (作用素)。
            apply_func (Callable[[int, int, F], None]): セグメント木の範囲更新関数 (apply(l, r, x))。
            edge (bool): True の場合、辺クエリ (u 直上の辺を含まない) として処理する。
        """
        l = self.vid[u]
        r = self.vid[u] + self.size[u]
        if edge:
            l += 1
        if l < r:
            apply_func(l, r, x)
    
    def set(self, u: int, set_func, x) -> None:
        """頂点 u の値を更新する。

        Args:
            u (int): 更新対象の頂点。
            set_func (Callable[[int, tuple[T, T]], None]): セグメント木の一点更新関数。
            x (T): 更新後の値。
        """
        set_func(self.vid[u], (x, x))

    def set_edge_by_id(self, edge_id: int, set_func, x) -> None:
        """入力時の辺 ID を指定して、辺の重みを更新する。

        Args:
            edge_id (int): E に与えられた辺のインデックス。
            set_func (Callable[[int, tuple[T, T]], None]): セグメント木の一点更新関数。
            x (T): 更新後の重み。
        """
        child = self.edge_to_child[edge_id]
        set_func(self.vid[child], (x, x))
    
    def get(self, u: int, get_func):
        """頂点 u の現在の値を取得する。

        Args:
            u (int): 取得対象の頂点。
            get_func (Callable[[int], tuple[T, T]]): セグメント木の一点取得関数。

        Returns:
            T: 頂点 u の現在の値。
        """
        val_pair = get_func(self.vid[u])
        return val_pair[0]

    def get_edge_by_id(self, edge_id: int, get_func):
        """入力時の辺 ID を指定して、辺の現在の重みを取得する。

        Args:
            edge_id (int): E に与えられた辺のインデックス。
            get_func (Callable[[int], tuple[T, T]]): セグメント木の一点取得関数。

        Returns:
            T: 指定された辺の現在の重み。
        """
        child = self.edge_to_child[edge_id]
        val_pair = get_func(self.vid[child])
        return val_pair[0]
    
    def make_v(self, original_values: list, e, edge: bool = False):
        """元の順序の値を、HLD順に並べ替えた (forward, backward) のペアリストに変換する。

        セグメント木の初期化用データを作成する際に使用します。

        Args:
            original_values (list): 元の順序の値リスト。
                頂点クエリの場合は頂点 0, 1, ..., N-1 の値 (長さ N)。
                辺クエリの場合は入力された辺 0, 1, ..., M-1 の値 (長さ N-1)。
            e (T): 単位元。辺クエリで根に対応する位置を埋めるために使用。
            edge (bool): 辺重みのリストを作成する場合は True。

        Returns:
            list[tuple[T, T]]: セグ木構築用の (val, val) のリスト。
        """
        if not edge:
            # 頂点クエリの場合、頂点数とリストの長さが一致することを確認
            assert len(original_values) == self.N, f"Expected length {self.N}, but got {len(original_values)}"
            hld_ordered: list = [original_values[0]] * self.N # 型推論のための仮初期化
            for i, val in enumerate(original_values):
                hld_ordered[self.vid[i]] = val
        else:
            # 辺クエリの場合、根の補完用 e が必須であり、リストの長さは N-1 であることを確認
            if e is None: # assertの代わりに明示的なif
                raise ValueError("Edge queries require identity element e")
            assert len(original_values) == self.N - 1, f"Expected length {self.N-1}, but got {len(original_values)}"
            hld_ordered = [e] * self.N
            for i, val in enumerate(original_values):
                child = self.edge_to_child[i]
                hld_ordered[self.vid[child]] = val
                
        return [(x, x) for x in hld_ordered]
    
    @staticmethod
    def make_op(op):
        """非可換演算を (forward, backward) のペアで扱えるようにラップする。

        セグメント木の初期化時に渡す演算関数を作成します。
        forward は左から右 (a -> b)、backward は右から左 (b -> a) の順で演算を適用します。

        Args:
            op (Callable[[T, T], T]): 元の二項演算 (例: 行列の積、文字列の結合など)。

        Returns:
            Callable[[tuple[T, T], tuple[T, T]], tuple[T, T]]: 
                ペアを受け取りペアを返す、セグメント木用の二項演算関数。
        """
        return lambda a, b: (op(a[0], b[0]), op(b[1], a[1]))
    
    @staticmethod
    def make_e(e):
        """単位元を (forward, backward) のペアにする。

        セグメント木の初期化時に渡す単位元を作成します。

        Args:
            e (T): 元の演算における単位元。

        Returns:
            tuple[T, T]: (e, e) のペア。
        """
        return (e, e)
    
    @staticmethod
    def make_mapp(mapp):
        """作用関数を (forward, backward) ペア用にラップします。

        HLDで非可換なパスを扱う際、セグメント木のデータ S が (fwd, bwd) のペアになるため、
        単一の作用素 f を両方の要素に適用するように変換します。

        Args:
            mapp (Callable[[F, T], T]): 元の作用関数。
                第1引数に作用素 (F)、第2引数にデータ (T) を受け取り、新しいデータを返すもの。

        Returns:
            Callable[[F, Tuple[T, T]], Tuple[T, T]]: ラップされた作用関数。
        """
        return lambda f, x: (mapp(f, x[0]), mapp(f, x[1]))
    
    @staticmethod
    def make_comp(comp):
        """作用素の合成関数を、インターフェースの対称性のためにラップします。

        作用素 F は HLD によるペア化の影響を受けないため、基本的には引数をそのまま返します。

        Args:
            comp (Callable[[F, F], F]): 元の合成関数。
                第1引数に新しい作用素、第2引数に古い作用素を受け取り、合成された作用素を返すもの。

        Returns:
            Callable[[F, F], F]: 入力された合成関数をそのまま返します。
        """
        return comp
    
    @staticmethod
    def make_id(id):
        """作用素の単位元を、インターフェースの対称性のためにラップします。

        データ S と異なり、作用素 F はペア化されないため、値は変更されません。

        Args:
            f (F): 元の作用素の単位元 (identity element)。

        Returns:
            F: 入力された単位元をそのまま返します。
        """
        return id
    
# -----------------------------------------------------------------
# HLD 使用例 (Usage Examples)
# -----------------------------------------------------------------

"""
1. 準備: セグメント木 (一点更新・パス集約)
   例: パス上の行列積や最大値など (非可換対応)
"""
# def op(a, b): return a+b
# e = 0
# S = SegTree(
#     hld.make_op(op),
#     hld.make_e(e),
#     hld.make_v(v, e)
# )


"""
2. 準備: 遅延セグメント木 (範囲更新・パス更新)
   例: パス一括加算、パス一括塗りつぶし
"""
# def op(a, b): return a+b
# e = 0
# def mapp(f, x): return f+x
# def comp(f, g): return f+g
# id = 0
# S = LazySegTree(
#     hld.make_op(op),
#     hld.make_e(e),
#     hld.make_mapp(mapp),
#     hld.make_comp(comp),
#     hld.make_id(id),
#     hld.make_v(v, e)
# )


"""
3. 頂点クエリ (Vertex Queries)
"""
# --- 値の更新 (一点) ---
# hld.set(u, S.set, x)

# --- パス集約 (u から v への順序を考慮) ---
# res = hld.prod_path(u, v, e, S.prod, op)

# --- 部分木集約 ---
# res = hld.prod_subtree(u, e, S.prod, op)

# --- パス一括更新 (遅延セグ木使用) ---
# hld.apply_path(u, v, x, S.apply)

# --- 部分木一括更新 (遅延セグ木使用) ---
# hld.apply_subtree(u, x, S.apply)


"""
4. 辺クエリ (Edge Queries)
   辺の値を「根から遠い方の頂点」に持たせて管理します。
   edge=True を指定することで LCA (頂点) を自動的に除外します。
"""
# --- 準備 (辺の初期値リストから HLD 順のペアリストを作成) ---
# S = SegTree(
#     hld.make_op(op),
#     hld.make_e(e),
#     hld.make_v(edge_weights, e, edge=True)
# )

# --- 辺の値の更新 (入力時の i 番目の辺を指定) ---
# hld.set_edge_by_id(i, S.set, new_w)

# --- パス上の辺の集約 ---
# res = hld.prod_path(u, v, e, S.prod, op, edge=True)

# --- 頂点 u の直下にある部分木内の辺をすべて更新 ---
# hld.apply_subtree(u, x, S.apply, edge=True)


"""
5. その他便利機能 (Tree Metrics)
"""
# --- LCA (最近共通祖先) ---
# lca = hld.get_lca(u, v)

# --- 距離 (重みなしエッジ数 / 重みあり距離) ---
# 辺に重みがない場合は同じ結果になる。
# dist_steps = hld.get_edge_dist(u, v)
# dist_weighted = hld.get_dist(u, v)

# --- K個上の祖先 (存在しなければ -1) ---
# anc = hld.kth_ancestor(u, k)

# --- パス上のジャンプ (u から v 方向へ k ステップ移動) ---
# target = hld.jump(u, v, k)

def ctypes(li, types):
    assert len(li) == len(types)
    return [t(a) for a, t in zip(li, types)]
def tinput(*types):
    li = input().split()
    return ctypes(li, types)
def qinput(*types):
    li = input().split()
    t = int(li[0])
    if len(li) == 1: return t, types[t-1][0](li[1])
    else: return t, ctypes(li[1:], types[t-1])
N, M, si, ti = tinput(int, int, _int, _int)
FID = DSU(N)
UV = []
for _ in range(M):
    u, v = tinput(_int, _int)
    FID.merge(u, v)
    UV.append((u, v))

if not FID.same(si, ti):
    print(-1)
V = []
for i in range(N):
    if not FID.same(si, i): continue
    V.append(i)
N = FID.size(si)
pos = {x: e for e, x in enumerate(V)}
si = pos[si]
ti = pos[ti]
E = [[] for _ in range(N)]
edges = []
D = DSU(N)
for u, v in UV:
    u, v = pos[u], pos[v]
    if not FID.same(si, u): continue
    if u > v: u, v = v, u
    if D.same(u, v): continue
    D.merge(u, v)
    edges.append((u, v))

hld = HLD(N, edges, 0)
def op(a, b): return a+b
e = 0
def mapp(f, x): return f+x
def comp(f, g): return f+g
id = 0
S = LazySegTree(
    hld.make_op(op),
    hld.make_e(e),
    hld.make_mapp(mapp),
    hld.make_comp(comp),
    hld.make_id(id),
    hld.make_v([0]*N, e)
)

E = [[] for _ in range(N)]
D = DSU(N)
eset = set()
for u, v in UV:
    if not D.same(si, u): continue
    u, v = pos[u], pos[v]
    if u > v: u, v = v, u
    E[u].append(v)
    E[v].append(u)
    if D.same(u, v):
        eset.add((u, v))
        hld.apply_path(u, v, 1, S.apply)
    D.merge(u, v)
for e, (u, v) in enumerate(edges):
    if S.get(e)[0] > 0:
        eset.add((u, v))

q = deque([si])
dist = [0]*N
vis = [0]*N
vis[si] = 0
dist[si] = 0
while q:
    i = q.popleft()
    vis[i] = 2
    for j in E[i]:
        if vis[j] == 2: continue
        if i > j:
            loop = 1 if (j, i) in eset else 0
        else:
            loop = 1 if (i, j) in eset else 0
        if dist[j] < dist[i]+loop:
            dist[j] = dist[i]+loop
        if vis[j]: continue
        vis[j] = 1
        q.append(j)
print(dist[ti])