using namespace std;
enum event_type
{
    FUEL,
    LEAK,
    GAS,
    MECHANIC,
    GOAL
};
struct event
{
    event_type type;
    int fc;
};
map<int, vector<event>> events_at;
int n;
bool simulate(double tank_vol)
{
    int dist = 0, delta = 0, fc_rate = 0, leak_rate = 0;
    double gas_left = tank_vol;
    vector<event> events;
    for (auto kv : events_at)
    {
        delta = kv.first - dist;
        dist = kv.first;
        events = kv.second;
        gas_left -= ((fc_rate * delta / 100.0) + leak_rate * delta);
        if (gas_left < 0)
            return false;
        for (auto e : events)
        {
            if (e.type == FUEL)
                fc_rate = e.fc;
            else if (e.type == LEAK)
                ++leak_rate;
            else if (e.type == GAS)
                gas_left = tank_vol;
            else if (e.type == MECHANIC)
                leak_rate = 0;
        }
    }
    return true;
}
double bsearch(double l, double r)
{
    while ((r - l) > 0.000000001)
    {
        double mid = (l + r) / 2.0;
        if (simulate(mid))
            r = mid;
        else
            l = mid;
    }
    return l;
}
event_type ecast(string raw_type)
{
    if (raw_type == "Fuel")
        return FUEL;
    if (raw_type == "Leak")
        return LEAK;
    if (raw_type == "Gas")
        return GAS;
    if (raw_type == "Mechanic")
        return MECHANIC;
    else
        return GOAL;
}
int main(void)
{
    int d;
    string cmd, trash;
    while (true)
    {
        cin >> d >> cmd >> trash >> n;
        if (cmd == "Fuel" and n == 0)
            break;
        events_at[d].push_back({ecast(cmd), n});
        while (true)
        {
            cin >> d >> cmd;
            if (cmd == "Fuel" or cmd == "Gas")
                cin >> trash;
            if (cmd == "Fuel")
                cin >> n;
            events_at[d].push_back({ecast(cmd), n});
            if (cmd == "Goal")
                break;
        }
        cout << setprecision(3) << fixed << bsearch(0, INT_MAX) << endl;
        events_at.clear();
    }
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using iic = tuple<int, int, char>;
const int NMAX = 1e3 + 11;
iic directions[4] = {{1, 0, 'D'}, {-1, 0, 'U'}, {0, 1, 'R'}, {0, -1, 'L'}};
ii start, target;
char lab[NMAX][NMAX];
bool visited[NMAX][NMAX];
int n, m;
inline bool valid(int row, int col)
{
    return (row >= 0 and row < n and col >= 0 and col < m and
            lab[row][col] != '#');
}
void reconstruct_path(ii x, const map<ii, pair<ii, char>> &parent)
{
    ii end = x;
    string res = "";
    do
    {
        res += parent.at(end).second;
        end = parent.at(end).first;
    } while (end != start);
    reverse(res.begin(), res.end());
    cout << "YES" << endl;
    cout << res.length() << endl;
    cout << res << endl;
}
void bfs(void)
{
    list<ii> q;
    map<ii, pair<ii, char>> parent;
    visited[start.first][start.second] = 1;
    q.push_back(start);
    while (!q.empty())
    {
        auto [i, j] = q.front();
        q.pop_front();
        for (auto [di, dj, dir] : directions)
        {
            if (valid(i + di, j + dj) and !visited[i + di][j + dj])
            {
                ii x = {i + di, j + dj};
                parent[x] = {{i, j}, dir};
                if (x == target)
                {
                    reconstruct_path(x, parent);
                    return;
                }
                visited[i + di][j + dj] = true;
                q.push_back(x);
            }
        }
    }
    cout << "NO" << endl;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> lab[i][j];
            if (lab[i][j] == 'A')
                start = {i, j};
            else if (lab[i][j] == 'B')
                target = {i, j};
        }
    }
    bfs();
    return 0;
}

using namespace std;
using ii = pair<int, int>;
const int NMAX = 1e3 + 11;
int n, m;
bool wall[NMAX][NMAX];
vector<ii> directions = {{+1, 0}, {-1, 0}, {0, +1}, {0, -1}};
inline bool valid(int i, int j)
{
    return 0 <= i and i < n and 0 <= j and j < m and not wall[i][j];
}
vector<ii> neighbors(ii u)
{
    vector<ii> ans;
    auto [i, j] = u;
    for (auto [di, dj] : directions)
        if (valid(di + i, dj + j))
            ans.push_back({i + di, j + dj});
    return ans;
}
void dfs(ii u)
{
    auto [i, j] = u;
    wall[i][j] = true;
    for (auto v : neighbors(u))
        dfs(v);
}
int main(void)
{
    int ans = 0;
    char c;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> c;
            wall[i][j] = (c == '#');
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (not wall[i][j])
            {
                ans += 1;
                dfs({i, j});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
vector<string> pat;
ii DUMMY = {-1, -1};
vector<ii> directions = {{+1, 0}, {-1, 0}, {0, +1}, {0, -1}};
vector<ii> neighbors(ii u)
{
    vector<ii> ans;
    for (auto [dr, dc] : directions)
        ans.emplace_back(u.first + dr, u.second + dc);
    return ans;
}
void bfs(ii start, int n)
{
    int level = n;
    set<ii> visited;
    queue<ii> frontier;
    frontier.push(start);
    frontier.push(DUMMY);
    visited.insert(start);
    while (not frontier.empty())
    {
        ii u = frontier.front();
        frontier.pop();
        if (u == DUMMY)
        {
            level--;
            if (level == -1)
                return;
            frontier.push({-1, -1});
            continue;
        }
        pat[u.first][u.second] = to_string(level)[0];
        for (auto v : neighbors(u))
        {
            if (visited.find(v) == visited.end())
            {
                visited.insert(v);
                frontier.push(v);
            }
        }
    }
}
int main(void)
{
    int n;
    cin >> n;
    pat.resize(2 * n + 1);
    for (auto &row : pat)
        row.resize(2 * n + 1, ' ');
    bfs({n, n}, n);
    for (int j = 0, p = pat.size(); j < p; ++j)
    {
        for (int i = 0, m = pat[j].size(); i < m; ++i)
        {
            cout << pat[j][i];
            if (pat[j][i] == '0' and i >= n)
                break;
            cout << ' ';
        }
        cout << endl;
    }
    return 0;
}

using namespace std;
vector<char> vowels = {'a', 'e', 'i', 'o', 'u', 'y'};
bool isvowel(char c)
{
    c = tolower(c);
    return find(vowels.begin(), vowels.end(), c) != vowels.end();
}
bool isconsonant(char c)
{
    c = tolower(c);
    return find(vowels.begin(), vowels.end(), c) == vowels.end();
}
int main(void)
{
    string s, ans;
    cin >> s;
    for (auto c : s)
    {
        if (isvowel(c))
            continue;
        else if (isconsonant(c))
        {
            ans += ".";
            ans += tolower(c);
        }
        else
            ans += c;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi cnt(n + 1);
        for (int i = 0; i < n; ++i)
        {
            int ai;
            cin >> ai;
            cnt[ai]++;
        }
        multiset<int, greater<int>> s;
        for (int i = 1; i <= n; ++i)
            if (cnt[i] > 0)
                s.insert(cnt[i]);
        int cur = *s.begin(), ans = 0;
        for (auto x : s)
        {
            ans += min(cur, x);
            cur = min(cur, x);
            cur--;
            if (cur == 0)
                break;
        }
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
const int MMAX = 1e4 + 11;
int n, m, a[MMAX];
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int pos, ans;
    string line;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        getline(cin, line);
        stringstream ss(line);
        pos = 0;
        while (ss >> a[pos])
            ++pos;
        m = pos;
        ans = 0;
        for (int i = 0; i < m - 1; ++i)
            for (int j = i + 1; j < m; ++j)
                ans = max(ans, gcd(a[i], a[j]));
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, m;
vi g[NMAX], parity[2];
void bfs(int src)
{
    vi visited(n + 1, false), dist(n + 1, 0);
    queue<int> frontier;
    visited[src] = true;
    frontier.push(src);
    dist[src] = 0;
    parity[0].push_back(src);
    while (not frontier.empty())
    {
        auto u = frontier.front();
        frontier.pop();
        for (auto v : g[u])
        {
            if (not visited[v])
            {
                dist[v] = dist[u] + 1;
                parity[dist[v] % 2].push_back(v);
                visited[v] = true;
                frontier.push(v);
            }
        }
    }
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i <= n; ++i)
            g[i].clear();
        parity[0].clear(), parity[1].clear();
        for (int i = 0; i < m; ++i)
        {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        bfs(1);
        int ix = 1;
        if ((int)parity[0].size() < (int)parity[1].size())
            ix = 0;
        cout << (int)parity[ix].size() << endl;
        for (auto u : parity[ix])
            cout << u << " ";
        cout << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
struct dsu
{
    vi parent;
    vi sz;
    dsu(int n)
    {
        parent.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            parent[i] = i;
            sz[i] = 1;
        }
    }
    int find_set(int a)
    {
        if (parent[a] == a)
            return a;
        return (parent[a] = find_set(parent[a]));
    }
    void union_set(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if (a != b)
        {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }
    int get_size(int a) { return sz[find_set(a)]; }
};
int main(void)
{
    int n, m, ki, a0, a;
    cin >> n >> m;
    dsu cc(n);
    for (int i = 0; i < m; ++i)
    {
        cin >> ki;
        for (int j = 0; j < ki; ++j)
        {
            if (j == 0)
                cin >> a0;
            else
            {
                cin >> a;
                cc.union_set(a0, a);
            }
        }
    }
    for (int a = 1; a <= n; ++a)
    {
        cout << cc.get_size(a) << " ";
    }
    cout << endl;
    return 0;
}