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

const int N = 100010, M = 2000010;

int n, m;
int w[N];
int hs[N], ht[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];

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

void spfa(int h[], int dist[], int type)
{
   queue<int>q;
   if(type==0){
       q.push(1);
       st[1]=true;
       memset(dist,0x3f,sizeof dmin);
       dist[1]=w[1];
   }
   else{
       q.push(n);
       st[n]=true;
       memset(dist,-0x3f,sizeof dmax);
       dist[n]=w[n];
   }
   while(q.size()){//队列不空
       int t=q.front();
       q.pop();
       st[t]=false;
       for(int i=h[t];~i;i=ne[i]){
        int j=e[i];
        if(type==0&&min(w[j],dist[t])<dist[j]||type==1&&max(w[j],dist[t])>dist[j]){
            if(type==0){
                dist[j]=min(w[j],dist[t]);
                q.push(j);
                st[j]=true;
            }
            else{
                dist[j]=max(w[j],dist[t]);
                q.push(j);
                st[j]=true;
            }
        }
    } 
   }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    memset(hs, -1, sizeof hs);
    memset(ht, -1, sizeof ht);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(hs, a, b), add(ht, b, a);//反向建边
        if (c == 2) add(hs, b, a), add(ht, a, b);
    }

    spfa(hs, dmin, 0);
    spfa(ht, dmax, 1);

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);

    printf("%d\n", res);

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 155;
const double INF = 1e20;

int n;
PDD q[N];
double d[N][N];
double maxd[N];
char g[N][N];

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;//每个点的横纵坐标值
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i == j) d[i][j] = 0;
            else if (g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]);
            else d[i][j] = INF;

    for (int k = 0; k < n; k ++ )
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    double r1 = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            if (d[i][j] < INF / 2)//联通
                maxd[i] = max(maxd[i], d[i][j]);
        r1 = max(r1, maxd[i]);
    }

    double r2 = INF;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (d[i][j] > INF / 2)//不联通
                r2 = min(r2,maxd[i]+get_dist(q[i],q[j])+maxd[j]);

    printf("%.6f\n", max(r1, r2));

    return 0;
}

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

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];   // first存查询的另外一个点，second存查询编号

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

void dfs(int u, int fa)//先预处理距离数组
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x)
{
    return (p[x] == x)? x : p[x] = find(p[x]);
}

void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }

    for (vector<PII>::iterator item=query[u].begin();item!=query[u].end();item++)
    {
        int y = item->first, id = item->second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    st[u] = 2;//以u为根节点的所有子树已处理完毕
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);

    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}

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

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];   // first存查询的另外一个点，second存查询编号

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

void dfs(int u, int fa)//先预处理距离数组
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x)
{
    return (p[x] == x)? x : p[x] = find(p[x]);
}

void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }

    for (vector<PII>::iterator item=query[u].begin();item!=query[u].end();item++)
    {
        int y = item->first, id = item->second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    st[u] = 2;//以u为根节点的所有子树已处理完毕
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);

    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N];
int fa[N][25];//f[i][j]代表i这个点往上跳2的j次方步数的点


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

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;//设置哨兵
    depth[root]=1;
    queue<int>q;
    q.push(root);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(depth[t]+1<depth[j]){
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<20;k++){
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca(int a, int b)
{
    if(depth[a]<depth[b])swap(a,b);
    for(int k=19;k>=0;k--){
        if(depth[fa[a][k]]>=depth[b])//跳出去fa[a][k]=0,depth[0]=0肯定小于depth[b]，不执行
        a=fa[a][k];
    }
    if(a==b)return a;//同一个点直接返回
    for(int k=19;k>=0;k--){
        if(fa[a][k]!=fa[b][k]){//跳出去是等于不用管
          a=fa[a][k];
          b=fa[b][k];
        }
    }
    return fa[a][0];
}

int main()
{
    scanf("%d", &n);
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

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

bool dfs(int u, int c, int limit)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(w[i]<=limit)continue;
        if(color[j]){
            if(color[j]==c)return false;
        }
        else{
            if(!dfs(j,3-c,limit))return false;
        }
    }
    return true;
}

bool check(int mid)//判断大于mid边是不是二分图
{
    memset(color, 0, sizeof color);//注意清空
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1,mid))return false;
        }
    }
   return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", l);
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int preorder[N], inorder[N];
int postorder[N], cnt;
//返回值是否创建成功 
bool build(int il, int ir, int pl, int pr, int type)//把这个子树的根节点加进去 
{
    if (il > ir) return true;//这个创造好了，下面没结点了，肯定创造成功 

    int root = preorder[pl];
    int k;//设置在外面
    if (type == 0)
    {
        for (k = il; k <= ir; k ++ )
            if (inorder[k] == root)
                break;  //先找到根 
        if (k > ir) return false;
    }
    else
    {
        for (k = ir; k >= il; k -- ) //从右到左遍历
            if (inorder[k] == root)
                break;
        if (k < il) return false;
    }

    bool res = true;
    if (!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) res = false;//先递归遍历左子树 
    if (!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type)) res = false;//在递归遍历右子树 

    postorder[cnt ++ ] = root;
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> preorder[i];
        inorder[i] = preorder[i];
    }

    sort(inorder, inorder + n);

    if (build(0, n - 1, 0, n - 1, 0))
    {
        puts("YES");
        cout << postorder[0];
        for (int i = 1; i < n; i ++ ) cout << ' ' << postorder[i];
        cout << endl;
    }
    else //判断是否为镜像，镜像是相反的存 
    {
        reverse(inorder, inorder + n);
        cnt = 0;//再重新从小到大存 
        if (build(0, n - 1, 0, n - 1, 1))
        {
            puts("YES");
            cout << postorder[0];
            for (int i = 1; i < n; i ++ ) cout << ' ' << postorder[i];
            cout << endl;
        }
        else puts("NO");
    }
    return 0;
}

#include <cstring>
#include <iostream>

using namespace std;

const int N = 25;

int n;
int l[N], r[N];
bool has_father[N];
int maxk, maxid;

void dfs(int u, int k)
{
    if (u == -1) return;

    if (k > maxk)
    {
        maxk = k;
        maxid = u;
    }

    dfs(l[u], k * 2);
    dfs(r[u], k * 2 + 1);
}

int main()
{
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);

    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        string a, b;
        cin >> a >> b;
        if (a != "-") l[i] = stoi(a), has_father[l[i]] = true;
        if (b != "-") r[i] = stoi(b), has_father[r[i]] = true;
    }

    int root = 0;
    while (has_father[root]) root ++ ;//找到根节点

    dfs(root, 1);

    if (maxk == n) printf("YES %d\n", maxid);
    else printf("NO %d\n", root);

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int n;
int l[N], r[N];
int a[N], w[N];
int k;
int tr[N];
void dfs(int u)
{
    if(u==-1)return;
    dfs(l[u]);
    w[u]=a[k++];
    dfs(r[u]);
}

void bfs()
{
    queue<int>q;
    q.push(0);
    int cnt=1;
    tr[0]=0;//存的是序号
    while(q.size()){
        int t=q.front();
        q.pop();
        if(l[t]!=-1){
            tr[cnt++]=l[t];
            q.push(l[t]);
        }
        if(r[t]!=-1){
            tr[cnt++]=r[t];
            q.push(r[t]);
        }
    }
    cout<<w[tr[0]];
    for (int i = 1; i < cnt; i ++ )
    cout<<' '<<w[tr[i]];
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> l[i] >> r[i];
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);//排完序就是中序遍历结果

    dfs(0);
    bfs();

    return 0;
}

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

int a[15]={0,1,2,3,4,5,6,7,8,9};
int n;
int ans;
int getint(int s,int e){
    int res=0;
    for(int i=s;i<=e;i++){
        res=res*10+a[i];
    }
    return res;
}
int main()
{
    cin>>n;
    do{
        for (int i = 1; i <= 7; i ++ ){
            int a1=getint(1,i);
            if(a1>n)continue; 
            for (int j = i+1; j <= 8; j ++ ){
               {
                    int b=getint(i+1,j),c=getint(j+1,9);
                    if(b%c)continue;
                    if(a1+b/c==n){
                        ans++;
                    }
                }
            }
        }

    }while(next_permutation(a+1,a+1+9));
    cout<<ans<<endl;
    return 0;
}