#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, (T)x); }
template<class T, class U, typename... W> void init(vector<T> &v, U x, size_t n, W... m) { v=vector<T>(n);  for(auto& a : v) init(a, x, m...); }

int n;
vector<ll> d; vector<int> mtl;
vector<vector<int>> edges;
vector<int> par;
vector<bool> marked;

int mintoleaf(int u, int p){
    if (mtl[u]!=-1) return mtl[u];
    int ret = n+1;
    for(int v : edges[u]) if (v !=p){
            umin(ret, 1 + mintoleaf(v, u));
        }
    if (edges[u].size() == 1)
        ret = 0;
    return mtl[u] = ret;
}

void dfs1(int u, int p){
    for(int v : edges[u]) if (v !=p){
            d[v] = d[u]+1;
            par[v] = u;
            dfs1(v, u);
        }
}

int dfs(int u, int p, int e){
    d[u] = e;
    vector<pii> o;
    for(int v : edges[u]) if (v != p){
            o.emplace_back(mintoleaf(v, u), v);
            if (marked[v]) o.back().first = 1e9;
        }
    sort(o.begin(), o.end());
    int start = e+1;
    for(auto it : o){
        int dist = dfs(it.second, u, start);
        start = dist + 1;
    }
    return start;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
    cin >> n;
    edges.resize(n+1);
    d.resize(n+1);
    mtl.resize(n+1, -1);
    FOR(i, n-1){
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    int ondiag = 1;
    d.clear(); d.resize(n + 1);
    par.clear(); par.resize(n+1);
    dfs1(ondiag, -1);
    int dist = -1;
    ondiag = -1;
    FOR1(u, n) {
        if (d[u] > dist) {
            dist = d[u];
            ondiag = u;
        }
    }
    d.clear(); d.resize(n + 1);
    par.clear(); par.resize(n+1);
    dfs1(ondiag, -1);
    marked.clear(); marked.resize(n+1);

    dist = -1;
    int other = -1;
    FOR1(u, n){
        if (d[u] > dist){
            dist = d[u];
            other = u;
        }
    }

    marked[other] = 1;
    while(other!=ondiag){
        other = par[other];
        marked[other] = 1;
    }

    d.clear(); d.resize(n + 1);
    dfs(ondiag, -1, 1);

    FOR1(i, n)
        cout << d[i] << " "; cout << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}


/**
 * Author: Daniel
 * Created Time: 2020-12-06 23:54:03
**/

// time-limit: 2000
#include <bits/stdc++.h>

using namespace std;

#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define lowbit(x) (x & -x)
#define SZ(x) ((int)x.size())
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define SOS; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);

typedef long long LL;
typedef pair<int, int> PII;

template <typename A> using VE = vector<A>;
template <typename A> using HEAP = priority_queue<A>;
template <typename A, typename B> using PA = pair<A, B>;
template <typename A> using RHEAP = priority_queue<A, vector<A>, greater<A> >;
    
///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////

// check the limitation!!!
const int N = 100010, M = 1010;

int n;
string t, s;

bool check()
{
    string s = t, tt = "011";
    reverse(ALL(s));
    for (int i = 0; i < n; i ++ )
        if (s[i] != tt[i % 3])
            return false;
    return true;
}

// read the question carefully!!!
int main()
{
    SOS;

    cin >> n >> t;

    if (n == 1)
    {
        if (t[0] == '0') cout << (LL)1e10 << '\n';
        else if (t[0] == '1') cout << (LL)2e10 << '\n';
        else cout << "0\n";
        return 0;
    }
    
    while (SZ(s) < n + 10) s += "011";

    if (t[n - 2] == '1' && t[n - 1] == '1') t += "0", n += 1;
    else if (t[n - 2] == '0' && t[n - 1] == '1') t += "10", n += 2;

    if (!check())
    {
        cout << "0\n";
        return 0;
    }

    reverse(ALL(t));

    LL res = ((LL)1e10 - n / 3LL) + !(n % 3LL);
    cout << res << '\n';
    return 0;
}

// GOOD LUCK!!!
