A group of n cities is connected by a network of roads. There is an undirected road between every pair of cities, so there are $\frac{n \cdot(n - 1)}{2}$ roads in total. It takes exactly y seconds to traverse any single road.

A spanning tree is a set of roads containing exactly n - 1 roads such that it's possible to travel between any two cities using only these roads.

Some spanning tree of the initial network was chosen. For every road in this tree the time one needs to traverse this road was changed from y to x seconds. Note that it's not guaranteed that x is smaller than y.

You would like to travel through all the cities using the shortest path possible. Given n, x, y and a description of the spanning tree that was chosen, find the cost of the shortest path that starts in any city, ends in any city and visits all cities exactly once.


-----Input-----

The first line of the input contains three integers n, x and y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 10^9).

Each of the next n - 1 lines contains a description of a road in the spanning tree. The i-th of these lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) — indices of the cities connected by the i-th road. It is guaranteed that these roads form a spanning tree.


-----Output-----

Print a single integer — the minimum number of seconds one needs to spend in order to visit all the cities exactly once.


-----Examples-----
Input
5 2 3
1 2
1 3
3 4
5 3

Output
9

Input
5 3 2
1 2
1 3
3 4
5 3

Output
8



-----Note-----

In the first sample, roads of the spanning tree have cost 2, while other roads have cost 3. One example of an optimal path is $5 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2$.

In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is $1 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow 3$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from collections import defaultdict\nfrom collections import deque\nfrom functools import reduce\nn, x, y = [int(x) for x in input().split()]\nE = defaultdict(set)\nfor i in range(n-1):\n    u, v = [int(x) for x in input().split()]\n    E[u].add(v)\n    E[v].add(u)\n\nif x > y:\n    for v in E:\n        if len(E[v]) == n-1:\n            print((n-2)*y + x)\n            break\n        elif len(E[v]) > 1:\n            print((n-1)*y)\n            break\nelse:\n    visited = {v : False for v in E}\n    stack = [1]\n    topsorted = deque()\n    while stack:\n        v = stack.pop()\n        if visited[v]: continue\n        visited[v] = True\n        topsorted.appendleft(v)\n        stack.extend(E[v])\n    chopped = set()\n    ans = 0\n    for v in topsorted:\n        ans += max(0, len(E[v])-2)\n        if len(E[v]) > 2:\n            S = E[v].intersection(chopped)\n            S1 = {S.pop(), S.pop()}\n            for u in E[v]:\n                if not u in S1:\n                    E[u].remove(v)\n            E[v].clear()\n            E[v].update(S1)\n        chopped.add(v)\n    print(ans*y + (n-1-ans)*x)\n        \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14783