#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 210;
const int M = 20010, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][N];

void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
}

int main()
{
   cin >> n >> m >> k;
   int a, b, c;

   memset(d, 0x3f, sizeof d);
   for(int i = 1; i <= n; i++)
       d[i][i] = 0;

   for(int i = 0; i < m; i++)
   {
       cin >> a >> b >> c;
       d[a][b] = min(d[a][b], c);
   }
   floyd();
   while(k--)
   {
       cin >> a >> b;
       int ret = d[a][b];
       if(ret > INF / 2) cout << "impossible" << endl;
       else cout<< ret << endl;
   }
   return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010, M = 2 * N;
int e[M], ne[M], h[N], idx;
int color[N];
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int a)
{
    color[u] = a;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 - a)) return false;
        }
        else if(color[j] == a) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int a, b;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    bool flag = true;
    for(int i = 1; i <= n; i++)
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }
    if(flag) cout << "Yes";
    else cout << "No";
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2 * 100010, INF = 0x3f3f3f3f;
int dist[N];
int p[N];
int cnt;
int n, m;

struct Edge{
    int u, v, w;
    bool operator <(const Edge &W) const
    {
        return w < W.w;
    }
}edge[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kruskal()
{
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i ++)
    {
        int a = edge[i].u, b = edge[i].v, c = edge[i].w;
        a = find(a), b = find(b);
        if(a!=b)
        {
            p[a] = b;
            cnt++;
            res += c;
        }

    }
    if(cnt < n - 1) return INF;
    return res;
}

int main()
{

    cin >> n >> m;
    int u, v, w;
    for(int i = 0; i < m; i++)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    sort(edge, edge + m);
    for(int i = 1; i <= n; i++)
        p[i] = i;

    memset(dist, 0x3f, sizeof dist);

    int ret = kruskal();
    if(ret == INF) cout << "impossible";
    else cout << ret;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];
int INF = 0x3f3f3f3f;
int dist[N];
bool st[N];

int prim(int n)
{
    dist[1] = 0;
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        if(dist[t] == INF) return INF;
        st[t] = true;
        if(i) res += dist[t];
        for(int j = 1; j <= n; j++)
        {
            if(!st[j])
            {
                dist[j] = min(dist[j], g[j][t]);
            }
        }
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    int u, v, w;
    memset(g, 0x3f ,sizeof g);
    for(int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    memset(dist, 0x3f, sizeof dist);
    int t = prim(n);
    if(t == INF)  cout << "impossible";
    else cout << t;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6010;
int H[N];
int e[N], ne[N], h[N], idx;
bool has_father[N];
int f[N][2];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = H[u];
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    int a, b;
    for(int i = 1; i <= n; i++)
        cin >> H[i];

    for(int i = 1; i <= n - 1; i++)
    {
        cin >> a >> b;
        add(b, a);
        has_father[a] = true;
    }

    int root = 0;
    for(int i = 1; i <= n; i++) 
        if(!has_father[i])
        {
             root = i;
             break;
        }
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
const int V = 110;
int v[N], w[N], s[N];
int f[N];

int main()
{
    int nn, vv;
    cin >> nn >> vv;
    for(int i = 1; i <= nn; i ++)
        cin >> v[i] >> w[i] >>s[i];

    for(int i = 1; i <= nn; i ++)
        for(int j = vv; j >= v[i]; j--)
            for(int k = s[i]; k >= 1; k--)
            {
                if(j >= k * v[i]) f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
            }


    cout << f[vv];

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main()
{
    int n, s;
    cin >> n >> s;

    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = s; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[s]<< endl; 
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int f[N];

int main()
{
    int n, s;
    cin >> n >> s;

    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= s; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[s] << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;
int f[N][N];

int main()
{

    int n;
    cin >> n;

    f[1][1] = 1;

    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    cout << res;

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int g[N], f[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> g[i];

    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(g[j] < g[i]) f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}