using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n;
vi g[NMAX];
ii dfs(int u, int p, int d)
{
    ii ans = {d, u};
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        ans = max(ans, dfs(v, u, d + 1));
    }
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto [d1, u] = dfs(1, 0, 0);
    auto [d2, v] = dfs(u, 0, 0);
    cout << d2 << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, m;
    vi f;
    vector<vi> bs;
    cin >> n >> m;
    f.resize(n, 0), bs.resize(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b, --a, --b;
        bs[a].push_back(b);
    }
    auto dist = [n](int l, int r) -> int { return (r - l + n) % n; };
    for (int i = 0; i < n; ++i)
    {
        if ((int)bs[i].size() > 0)
        {
            int closest = *min_element(bs[i].begin(), bs[i].end(), [i, dist](int a, int b) {
                return dist(i, a) < dist(i, b);
            });
            f[i] = ((int)bs[i].size() - 1) * n + dist(i, closest);
        }
    }
    for (int start = 0; start < n; ++start)
    {
        int ans = 0;
        for (int delta = 0; delta < n; ++delta)
        {
            auto fi = f[(start + delta) % n];
            ans = max(ans, fi + (fi > 0) * delta);
        }
        cout << ans << " ";
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 2e5 + 11;
int n, dp1[NMAX], dp2[NMAX];
vi g[NMAX];
void solve(int u, int p = 0)
{
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        solve(v, u);
        dp2[u] += max(dp1[v], dp2[v]);
    }
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        auto v_choice = max(dp1[v], dp2[v]);
        dp1[u] = max(dp1[u], 1 + dp2[u] - v_choice + dp2[v]);
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 1;
    solve(root);
    cout << max(dp1[root], dp2[root]) << endl;
    return 0;
}

using namespace std;
bool is_upper(char c) { return 'A' <= c and c <= 'Z'; }
string lower(string s)
{
    string ans = s;
    for (int i = 0, len = s.size(); i < len; ++i)
        if (is_upper(s[i]))
            ans[i] += ('a' - 'A');
    return ans;
}
int main(void)
{
    string s1, s2;
    cin >> s1 >> s2;
    s1 = lower(s1);
    s2 = lower(s2);
    cout << (s1 == s2 ? 0 : (s1 > s2 ? 1 : -1)) << endl;
    return 0;
}

using namespace std;
using ll = long long;
ll n, k, A, B;
ll a[100010];
ll binary_search(ll low, ll high, ll target)
{
    auto p = [&](ll x) { return a[x] >= target; };
    while (low < high)
    {
        ll mid = low + (high - low) / 2;
        if (p(mid))
            high = mid;
        else
            low = mid + 1;
    }
    if (not p(low))
        return high + 1;
    return low;
}
ll divide_and_conquer(ll l, ll r)
{
    ll tl = binary_search(0, k - 1, l);
    ll tr = binary_search(0, k - 1, r + 1) - 1;
    if (tr < tl)
        return A;
    else
    {
        if ((r - l) == 0)
            return B * (tr - tl + 1) * 1;
        else
        {
            ll m = l + (r - l) / 2;
            return min(divide_and_conquer(l, m) + divide_and_conquer(m + 1, r),
                       B * (tr - tl + 1) * (r - l + 1));
        }
    }
}
ll solve(void)
{
    sort(a, a + k);
    return divide_and_conquer(0, (int)pow(2, n) - 1);
}
int main(void)
{
    ll ai;
    cin >> n >> k >> A >> B;
    for (int i = 0; i < k; ++i)
    {
        cin >> ai;
        a[i] = ai - 1;
    }
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ss = stringstream;
int initial[8];
int board[8];
bool valid(int nrow, int ncol)
{
    for (int col = 0; col < ncol; ++col)
    {
        if (board[col] == nrow)
            return false;
        if ((ncol - col) == (int)abs(nrow - board[col]))
            return false;
    }
    return true;
}
int current_score(void)
{
    int score = 0;
    for (int col = 0; col < 8; ++col)
        score += (board[col] - initial[col]) != 0;
    return score;
}
int backtrack(int col)
{
    int ans = INT_MAX;
    for (int row = 0; row < 8; ++row)
    {
        if (valid(row, col))
        {
            int last = board[col];
            board[col] = row;
            if (col < 7)
                ans = min(ans, backtrack(col + 1));
            else
                ans = min(ans, current_score());
            board[col] = last;
        }
    }
    return ans;
}
int main(void)
{
    string line;
    int t = 0;
    while (getline(cin, line) and line != "")
    {
        ++t;
        int row;
        ss rows(line);
        for (int i = 0; i < 8; ++i)
        {
            rows >> row;
            board[i] = initial[i] = row - 1;
        }
        cout << "Case " << t << ": " << backtrack(0) << endl;
        line = "";
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int l, m;
        vi left, right;
        cin >> l >> m;
        l *= 100;
        while (m--)
        {
            int len;
            string side;
            cin >> len >> side;
            if (side[0] == 'l')
                left.push_back(len);
            else
                right.push_back(len);
        }
        int lans = 0, rans = 0, cur_acc = 0;
        for (auto len : left)
        {
            if (cur_acc + len >= l)
            {
                lans++;
                cur_acc = len;
            }
            else
                cur_acc += len;
        }
        if (cur_acc > 0)
            ++lans;
        cur_acc = 0;
        for (auto len : right)
        {
            if (cur_acc + len >= l)
            {
                rans++;
                cur_acc = len;
            }
            else
                cur_acc += len;
        }
        if (cur_acc > 0)
            ++rans;
        cout << 2 * max(lans, rans) - (lans > rans ? 1 : 0) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using ii = array<ll, 2>;
const ll NMAX = 5e3 + 11;
ll x[NMAX];
ii mem[NMAX][NMAX];
bool vis[NMAX][NMAX];
ii dp(ll l, ll r, bool player)
{
    ii &ans = mem[l][r];
    ll lval = x[l];
    ll rval = x[r];
    if (r - l + 1 == 2)
    {
        ans[player] = max({lval, rval});
        ans[!player] = min({lval, rval});
        return ans;
    }
    if (vis[l][r])
        return ans;
    vis[l][r] = true;
    ii lans = dp(l + 1, r, !player);
    ii rans = dp(l, r - 1, !player);
    lans[player] += lval;
    rans[player] += rval;
    ans = lans[player] > rans[player] ? lans : rans;
    return ans;
}
int main(void)
{
    ll n;
    cin >> n;
    for (ll i = 0; i < n; ++i)
        cin >> x[i];
    cout << dp(0, n - 1, true)[true] << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int id(char c)
{
    switch (c)
    {
    case 'd':
        return 4;
    case 'r':
        return 3;
    case 'a':
        return 2;
    case 'h':
        return 1;
    default:
        return 0;
    }
}
ll solve(int n, string s, vll a)
{
    string t(" hard");
    vi sorted[5];
    fill(sorted, sorted + 5, vi(1, 0));
    for (int i = 1; i <= n; ++i)
    {
        int j = id(s[i]);
        if (j > 0)
            sorted[j].push_back(i);
    }
    for (int i = 1; i <= 4; ++i)
    {
        if ((int)sorted[i].size() == 0)
            return 0;
        sort(sorted[i].begin(), sorted[i].end());
    }
    vll dp(n + 2, 1e17);
    int fst = *sorted[id('h')].begin();
    sorted[0] = {-1, n + 1};
    dp[fst] = a[fst];
    dp[0] = 0;
    for (int i = fst + 1; i <= n; ++i)
    {
        int idd = id(s[i]);
        if (idd > 0)
        {
            auto &ans = dp[i];
            auto it = lower_bound(sorted[idd].begin(), sorted[idd].end(), i);
            ans = min(ans, dp[*prev(it)] + a[i]);
            it = lower_bound(sorted[idd - 1].begin(), sorted[idd - 1].end(), i);
            ans = min(ans, dp[(n + 2 + *prev(it)) % (n + 2)]);
        }
    }
    return dp[sorted[id('d')].back()];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vll a(n + 1);
    string s(n + 1, ' ');
    read_n(next(s.begin()), n);
    read_n(next(a.begin()), n);
    cout << solve(n, s, a) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const MOD = 1e9 + 7;
ll modpow(ll a, ll b)
{
    a %= MOD;
    ll ans = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        cout << modpow(a, b) << endl;
    }
    return 0;
}