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

using namespace std;

typedef pair<int, int> PII;

const int N=100010,M=300010;

int n,m,k,q;

int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 0});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}


int main()
{
    cin>>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);
    }

    cin>>k;

    for(int i=1;i<=k;i++)//建立超级源点,连接每个商店,且权值为0,即可达到每个商店都可以是起点的目的
    {
        int x;
        scanf("%d",&x);
        add(0,x,0);
    }

    cin>>q;

    dijkstra();

    for(int i=1;i<=q;i++)
    {
        int start;
        cin>>start;
        printf("%d\n",dist[start]);
    }
}

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

#define x first
#define y second

using namespace std;

const int N = 25010,M=160010;

typedef pair<int, int> PII;

int n,P,R,S;
int dist[N],din[N],id[N];//id[i]表示i的所属集合的编号,din[i]表示id为i的点的集合的入度;
vector<int> block[N];//block[i]存储的是id为i的点的集合
int idcnt;//id的编号分配
queue<int> q;//入度为0的集合编号入队
bool st[N];//最短路判重
int h[N], e[M], w[M], ne[M], idx;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u,int idn)
{
    id[u]=idn;
    block[idn].push_back(u);

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!id[j]) dfs(j,idn);
    }
}

void dijkstra(int tid)
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;

    for(int i=0;i<block[tid].size();i++)
    heap.push({dist[block[tid][i]],block[tid][i]});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int u=t.y;
        if(st[u]) continue;
        st[u]=true;

        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(id[j]!=id[u]&&--din[id[j]]==0) q.push(id[j]);

            if(dist[j]>dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                if(id[j]==id[u]) heap.push({dist[j],j});
            }
        }
    }
}

void topsort()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;

    for(int i=1;i<=idcnt;i++)
    if(!din[i]) q.push(i);

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        dijkstra(t);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin>>n>>R>>P>>S;

    for(int i=1;i<=R;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c),add(b,a,c);
    }

    for(int i=1;i<=n;i++)
    if(!id[i]) dfs(i,++idcnt);//划分集合的过程

    while(P--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
        din[id[b]]++;//b所属的集合入度+1
    }

    topsort();//拓步排序求dijkstra

    for(int i=1;i<=n;i++)
    if(dist[i]>0x3f3f3f3f/2) printf("NO PATH\n");
    else printf("%d\n",dist[i]);

    return 0;
} 

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

using namespace std;

const int N=1000010;

int n;
char str[N];
int ne[N];

int main()
{
    int T=1;
    while(cin>>n,n)
    {
        scanf("%s",str+1);
       for (int i = 2, j = 0; i <= n; i ++ )
        {
            while (j && str[i] != str[j + 1]) j = ne[j];
            if (str[i] == str[j + 1]) j ++ ;
            ne[i] = j;
        }

        printf("Test case #%d\n", T ++ );

        for(int i=1;i<=n;i++)
        {
            int t = i - ne[i];
            if (i % t == 0 && i / t > 1)
                printf("%d %d\n", i, i / t);
        }
        puts("");
    }

    return 0;
}

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

using namespace std;

const int N=110;

int g[N][N],level[N];
int dist[N];
bool st[N];
int n,m;

int dijkstra(int minx,int maxi)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);

    dist[0]=0;

    for(int i=1;i<=n+1;i++)
    {
        int t=-1;

        for(int j=0;j<=n;j++)
        if(!st[j]&&(t==-1||dist[t]>dist[j]))
        t=j;

        st[t]=true;

        for(int j=1;j<=n;j++)
        if(level[j]>=minx&&level[j]<=maxi)
        dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    return dist[1];
}

int main()
{
    cin>>m>>n;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++)
    {
        int p,l,x;
        g[i][i]=0;
        scanf("%d%d%d",&p,&l,&x);
        level[i]=l;
        g[0][i]=p;
        while(x--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][i]=min(g[a][i],b);
        }
    }

    int res=0x3f3f3f3f;
    for(int i=level[1]-m;i<=level[1]+m;i++) res=min(res,dijkstra(i,i+m));

    printf("%d",res);

    return 0;
}

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

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=150010;

int h[N],e[N],ne[N],w[N],idx,dist[N];
int n,m;
bool st[N];

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

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    dist[1]=0;

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int u=t.second;
        if(st[u]) continue;
        st[u]=true;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[u]+w[i]<dist[j])
            {
                heap.push({dist[u]+w[i],j});
                dist[j]=dist[u]+w[i];
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

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

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        insert(a,b,c);
    }

    printf("%d",dijkstra());
}

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

using namespace std;

const int N=510;

int g[N][N];
int dist[N];
bool st[N];
int n,m;

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    dist[1]=0;

    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        if(!st[j]&&(t==-1||dist[t]>dist[j]))
        t=j;

        st[t]=true;

        for(int j=1;j<=n;j++)
        dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }

    printf("%d",dijkstra());

    return 0;
}

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

using namespace std;

const int N=110,M=10010;

int n;
int q[N],d[N];
int h[N],e[M],ne[M],idx;

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

void topsort()
{
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    if(!d[i]) q[++tt]=i;

    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(!d[j]) q[++tt]=j;
        }
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);

    for(int i=1;i<=n;i++)
    {
        int k;
        while(cin>>k,k)
        {
            if(k==0) break;
            insert(i,k);
            d[k]++;
        }
    }

    topsort();

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

    return 0;
}

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

using namespace std;

const int N=100010;

int d[N],q[N];
int h[N],e[N],ne[N],idx;
int n,m;

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

bool topsort()
{
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    if(!d[i]) q[++tt]=i;

    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(!d[j]) q[++tt]=j;
        }
    }

    if(tt==n-1) return true;
    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        insert(a,b);
        d[b]++;
    }

    if(topsort()) for(int i=0;i<n;i++) printf("%d ",q[i]);
    else printf("-1");

    return 0;
}

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


using namespace std;

const int N = 10;

int n, m, k;
int g[N][N];
unordered_set<int> S;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


void dfs(int x, int y, int u, int num)
{
    if (u == k) S.insert(num);
    else
    {
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m)
                dfs(a, b, u + 1, num * 10 + g[a][b]);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &g[i][j]);

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            dfs(i, j, 0, g[i][j]);

    printf("%d\n", S.size());
    return 0;
}

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

using namespace std;

const int N=20;

int n,ans;
bool st[N],backup[N];

bool check(int a,int c)
{
    long long b=(long long)n*c-(long long)a*c;

    if(!a||!b||!c) return false;

    memcpy(backup,st,sizeof st);

    while(b)
    {
        int x=b%10;
        if(!x) return false; 
        if(backup[x]) return false;
        backup[x]=true;
        b/=10;
    }

    for(int i=1;i<=9;i++)
    if(!backup[i]) return false;

    return true;
}

void dfs_c(int u,int a,int c)
{
    if(u>9) return ;

    if(check(a,c)) ans++;

    for(int i=1;i<=9;i++)
    if(!st[i])
    {
        st[i]=true;
        dfs_c(u+1,a,c*10+i);
        st[i]=false;
    }
}

void dfs_a(int u,int a)
{
    if(a>=n) return ;

    dfs_c(u,a,0);

    for(int i=1;i<=9;i++)
    if(!st[i])
    {
        st[i]=true;
        dfs_a(u+1,a*10+i);
        st[i]=false;
    }
}

int main()
{
    cin>>n;

    dfs_a(1,0);

    printf("%d",ans);
}