#include<algorithm> 
#include<sstream>
#include<string> 
#include<vector> 
#include<iostream>
#include<cstdio>
using namespace std; 
  
#define FOR(i,a,b) for(int i = (a); i < (b); ++i) 
#define REP(i,n) FOR(i,0,n) 
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it) 
#define pb push_back 
#define all(x) (x).begin(),(x).end() 
#define CLEAR(x,with) memset(x,with,sizeof(x)) 
#define sz size() 
typedef long long ll; 

const int inf = 987654321;
int n, m, timestamp;
vector<int> adj[10000];
int no[10000], taste[10000];
int sol;

pair<int,int> solve(int here, int parent = -1)
{
    no[here] = timestamp++;
    int totalApples = taste[here];
    int minReached = no[here];
    REP(i,adj[here].sz)
    {
        int there = adj[here][i];
        if(there == parent) continue;
        if(no[there] != -1)
            minReached <?= no[there];
        else
        {
            pair<int,int> r = solve(there, here);
            if(r.second > no[here]) sol >?= r.first;
            totalApples += r.first;
            minReached <?= r.second;       
        }
    }
//    printf("solve(%d) = (%d,%d)\n", here, totalApples, minReached);
    return make_pair(totalApples, minReached);
}

int main()
{
    while(scanf("%d %d", &n, &m) == 2)
    {
        if(n == 0 && m == 0) break;
        REP(i,n) { adj[i].clear(); }
        CLEAR(no,-1);
        REP(i,m)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            --a; --b;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        REP(i,n) scanf("%d", &taste[i]);
        timestamp = 0;
        sol = -inf;
        pair<int,int> res = solve(0);
        if(sol == -inf)
            printf("No apple\n");
        else
            printf("%d\n", sol);
    }
}

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        if(n == 0) break;
        int m = 0;
        while(n > 0)
        {
            m = m * 2 + n % 2;
            n /= 2;
        }
        cout << m << endl;
    }
}

#include<queue>
#include<algorithm> 
#include<sstream>
#include<string> 
#include<vector> 
#include<iostream>
#include<cstdio>
using namespace std; 
  
#define FOR(i,a,b) for(int i = (a); i < (b); ++i) 
#define REP(i,n) FOR(i,0,n) 
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it) 
#define pb push_back 
#define all(x) (x).begin(),(x).end() 
#define CLEAR(x,with) memset(x,with,sizeof(x)) 
#define sz size() 
typedef long long ll; 

const int MAXV = 200;
struct NetworkFlow
{
  int flow[MAXV][MAXV], cap[MAXV][MAXV], totalFlow, V;
  NetworkFlow(int V): V(V) { CLEAR(cap,0); CLEAR(flow,0);totalFlow = 0; }
 
  void addEdge(int a, int b, int c) { cap[a][b] += c; }
 
  void push(int a, int b, int c) { flow[a][b] += c; flow[b][a] = - flow[a][b]; }
  int res(int a, int b) { return cap[a][b] - flow[a][b]; }
 
  int pushFlow(int source = 0, int sink = 1)
  {
    vector<int> pred(V, -1); queue<int> q;
    q.push(source); pred[source] = source;
    while(!q.empty() && pred[sink] == -1)
    {
      int u = q.front(); q.pop();
      for(int v = 0; v < V; ++v) if(res(u,v) > 0 && pred[v] == -1) { pred[v] = u; q.push(v); }
    }
    if(pred[sink] == -1) return 0;
    int h, amt = 987654321;
    h = sink; while(pred[h] != h) { amt <?= res(pred[h], h); h = pred[h]; }
    h = sink; while(pred[h] != h) { push(pred[h], h, amt); h = pred[h]; }
    totalFlow += amt;
    return amt;
  }
};

int main()
{
    int n, m, k;
    while(scanf("%d %d %d", &n, &m, &k) == 3)
    {
        if(n+m+k == 0) break;

        NetworkFlow* net = new NetworkFlow( 2 + n + m );
        REP(i,n)
        {
            int x;
            scanf("%d", &x);
            REP(j,x)
            {
                int course;
                scanf("%d", &course);
                --course;
                net->addEdge( 2+i, 2+n+course, 1);
            }
        }
        REP(i,m) net->addEdge(2+n+i, 1, k);
        int ret = -1;
        FOR(sol,1,m+1)
        {
            REP(i,n) net->addEdge(0, 2+i, 1);
            while(net->pushFlow());
            if(net->totalFlow < sol * n)
            {
                ret = sol-1;
                break;
            }
        }
        if(ret == -1) ret = m;
        printf("%d\n", ret);
    }
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        vector<int> ret(3);
       
        for (int i = 0; i < n; i++) {
            int v1, v2, v3;
            scanf("%d %d %d", &v1, &v2, &v3);
            vector<int> tmp(3, 0);
            tmp[0] = v1 + max(ret[1], ret[2]);
            tmp[1] = v2 + max(ret[0], ret[2]);
            tmp[2] = v3 + max(ret[0], ret[1]);
            ret = tmp;
        }
        cout << *max_element(ret.begin(), ret.end()) << endl;
    }
}

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int> > solve(int n) {
    vector<pair<int, int> > ret;
    for (int i = 2; ; i++) {
        int p = 0;
        while (n % i == 0) {
            n /= i;
            p++;
        }
        if (p) {
            ret.push_back(make_pair(i, p));
            if (n == 1) break;
        }
    }
    return ret;
}

int main() {
    int n, b;
    while (scanf("%d %d", &n, &b) == 2) {
        if (n == 0 && b == 0) break;
        vector<pair<int, int> > fact = solve(b);
        int ret = n + 1;

        for (int i = 0; i < fact.size(); i++) {
            int t = 0, now = n;
            while (now) {
                t += now / fact[i].first;
                now /= fact[i].first;
            }
            ret <?= (t / fact[i].second);
        }
        printf("%d\n", ret);
    }
}

#include<algorithm> 
#include<sstream>
#include<string> 
#include<vector> 
#include<iostream>
#include<cstdio>
#include<queue>
#include<set>
using namespace std; 
  
#define FOR(i,a,b) for(int i = (a); i < (b); ++i) 
#define REP(i,n) FOR(i,0,n) 
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it) 
#define pb push_back 
#define all(x) (x).begin(),(x).end() 
#define CLEAR(x,with) memset(x,with,sizeof(x)) 
#define sz size() 
typedef long long ll; 

const int dy[4] = { 1, -1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };
int n;
char board[501][501];
int depends[501][501];
bool seen[501][501];

void go(int y, int x)
{
    queue<pair<int,int> > q;
    seen[y][x] = true;
    q.push(make_pair(y, x));
    set<pair<int,int> > e;
    int size = 0;
    while(!q.empty())
    {
        ++size;
        int cy = q.front().first, cx = q.front().second;
        q.pop();
        REP(k,4)
        {
            int ny = cy + dy[k], nx = cx + dx[k];
            if(ny < 0 || nx < 0 || nx >= n || ny >= n) continue;
            if(board[ny][nx] == '.')
            {
                if(e.size() < 2) e.insert(make_pair(ny, nx));
            }
            else if(board[ny][nx] == 'W' && !seen[ny][nx])
            {
                seen[ny][nx] = true;
                q.push(make_pair(ny, nx));
            }
        }
    }
    if(e.sz == 1)
    {
        pair<int,int> pos = *e.begin();
        //printf("(%d,%d) => (%d,%d)\n", y,x,pos.first,pos.second);
        depends[pos.first][pos.second] += size;
    }
}

int main()
{
    while(scanf("%d", &n) == 1)
    {
        if(n == 0) break;
        REP(i,n) scanf("%s", board[i]);
        CLEAR(seen,0);
        CLEAR(depends,0);
        REP(i,n) REP(j,n) if(board[i][j] == 'W' && !seen[i][j]) go(i, j);
        int ret = 0;
        REP(i,n) REP(j,n) ret >?= depends[i][j];
        printf("%d\n", ret);
    }
}

#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 100000
#define epsilon (1e-9)

struct Point {
    double x, y;
};

int i, j, n, m;
double sol;
Point point[MAXN], *pt[MAXN], *swapt;

inline bool equal(double a, double b) {
    return (a - epsilon < b) && (b < a + epsilon);
}

double ccw(Point *a, Point *b, Point *c) {
    return (a->x * b->y + b->x * c->y + c->x * a->y) -
        (a->y * b->x + b->y * c->x + c->y * a->x);
}

double length(Point *a, Point *b) {
    return (a->x - b->x) * (a->x - b->x) +
        (a->y - b->y) * (a->y - b->y);
}

struct sf {
    double t;
    bool operator()(Point *lhs, Point *rhs) {
        t = ccw(pt[0], lhs, rhs);

        if(equal(t, 0)) {
            return length(pt[0], lhs) > length(pt[0], rhs);
        }
        else {
            return t > 0;
        }
    }
};

using namespace std;

int main() {
    double t;
    double aa, bb;
    int idx = 0, nextj;

    while(true) {
        scanf("%d", &n);
        if(n == 0) {
            break;
        }

        for(i = 0; i < n; ++ i) {
            scanf("%lf %lf", &point[i].x, &point[i].y);
            pt[i] = &point[i];

            if((pt[idx]->y) > (pt[i]->y)) {
                idx = i;
            }
        }

        swapt = pt[idx];
        pt[idx] = pt[0];
        pt[0] = swapt;

        stable_sort(pt + 1, pt + n, sf());

        m = 2;

        for(i = 2; i < n; ++ i) {
            while(m > 1) {
                t = ccw(pt[m - 2], pt[m - 1], pt[i]);

                if(!equal(t, 0) && t < 0) {
                    -- m;
                }
                else {
                    break;
                }
            }

            pt[m ++] = pt[i];
        }

        sol = 0; j = 0;
        for(i = 0; i < m; ++ i) {
            aa = length(pt[i], pt[j]);

            while(true) {
                nextj = (j + 1) % m;
                bb = length(pt[i], pt[nextj]);

                if(aa > bb) {
                    break;
                }
                else {
                    aa = bb;
                    j = nextj;
                }
            }

            if(sol < aa) {
                sol = aa;
            }
        }

        printf("%.2lf\n", sqrt(sol));
    }

    return 0;
}

#include <queue>
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

struct reaction {
    int from, to;
    reaction(int a = 0, int b = 0) : from(a), to(b) {}
};

int M, N, G, P;

string getString() {
    string ret;
    cin >> ret;
    return ret;
}

int main() {
    string name;

    while (cin >> M) {
        if (M == 0) break;

        map<string, int> table;
        vector <int> check(1 << M);
        vector <int> dpt(1 << M, 9999);

        for (int i = 0; i < M; i++) table[getString()] = i;
       
        cin >> N;

        vector<reaction> a(N);
        for (int i = 0; i < N; i++) {
            int from = 0, to = 0, k, l;
            scanf("%d %d", &k, &l);
            for (int j = 0; j < k; j++) from |= (1 << table[getString()]);
            for (int j = 0; j < l; j++) to |= (1 << table[getString()]);
            a.push_back(reaction(from, to));
        }
        int start = 0;

        cin >> G;
        for (int i = 0; i < G; i++) start |= (1 << table[getString()]);

        queue<int> Q;

        check[start] = 1, dpt[start] = 0;
        Q.push(start);

        while (!Q.empty()) {
            int now = Q.front(), next; Q.pop();
            for (int i = 0; i < a.size(); i++) {
                next = now | a[i].to;
                if ((now & a[i].from) == a[i].from && check[next] == 0) {
                    check[next] = 1;
                    dpt[next] = dpt[now] + 1;
                    Q.push(next);
                }
            }
        }

        cin >> P;
        for (int i = 0; i < P; i++) {
            int now = (1 << table[getString()]);
            int ret = 9999;
            for (int j = 0; j < (1 << M); j++)
                if ((j & now) == now) ret <?= dpt[j];

            if (ret == 9999) {
                cout << "No solution!" << endl;
            } else {
                cout << "LeastReaction(s): " << ret << endl;
            }
        }
    }
}