PAT – 第24页

1076. Forwards on Weibo (30)-PAT甲级真题（图的遍历bfs）

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=1000), the number of users; and L (<=6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:

M[i] user_list[i]

where M[i] (<=100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space.

Then finally a positive K is given, followed by K UserID’s for query.

Output Specification:

For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can triger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.

Sample Input:
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
Sample Output:
4
5

题目大意：给出每个用户关注的人的id，和转发最多的层数，求一个id发了条微博最多会有多少个人转发
分析：带层数的广度优先，因为一个用户只能转发一次，所以用inq判断当前结点是否入队过了，如果入队过了就不能重复入队（重复转发消息），inq 邻接表v 都可以使用int只存储id，queue的数据类型必须为node，同时保存它的id和layer层数，控制不超过L层～

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n, l, m, k;
struct node {
    int id, layer;
};
vector<vector<int>> v;
int bfs(node tnode) {
    bool inq[1010] = {false};
    queue<node> q;
    q.push(tnode);
    inq[tnode.id] = true;
    int cnt = 0;
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        int topid = top.id;
        for(int i = 0; i < v[topid].size(); i++) {
            int nextid = v[topid][i];
            if(inq[nextid] == false && top.layer < l) {
                node next = {nextid, top.layer + 1};
                q.push(next);
                inq[next.id] = true;
                cnt++;
            }
        }
    }
    return cnt;
}
int main() {
    scanf("%d %d", &n, &l);
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &m);
        for(int j = 0; j < m; j++) {
            int temp;
            scanf("%d", &temp);
            v[temp].push_back(i);
        }
    }
    scanf("%d", &k);
    int tid;
    for(int i = 0; i < k; i++) {
        scanf("%d", &tid);
        node tnode = {tid, 0};
        printf("%d\n", bfs(tnode));
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

int n, l, m, k;

struct node {

int id, layer;

};

vector<vector<int>> v;

int bfs(node tnode) {

bool inq[1010] = {false};

queue<node> q;

q.push(tnode);

inq[tnode.id] = true;

int cnt = 0;

while(!q.empty()) {

node top = q.front();

q.pop();

int topid = top.id;

for(int i = 0; i < v[topid].size(); i++) {

int nextid = v[topid][i];

if(inq[nextid] == false && top.layer < l) {

node next = {nextid, top.layer + 1};

q.push(next);

inq[next.id] = true;

cnt++;

}

return cnt;

}

int main() {

scanf("%d %d", &n, &l);

v.resize(n + 1);

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

scanf("%d", &m);

for(int j = 0; j < m; j++) {

int temp;

scanf("%d", &temp);

v[temp].push_back(i);

}

scanf("%d", &k);

int tid;

for(int i = 0; i < k; i++) {

scanf("%d", &tid);

node tnode = {tid, 0};

printf("%d\n", bfs(tnode));

}

return 0;

}

1034. Head of a Gang (30)-PAT甲级真题（连通分量、图的遍历dfs）

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 1:
2
AAA 3
GGG 3
Sample Input 2:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 2:
0

题目大意：给出1000条以内的通话记录A B和权值w，和阈值k，如果一个团伙人数超过2人并且通话总权值超过k，令团伙里面的自身权值的最大值为头目，输出所有满足条件的团伙的头目，和他们团伙里面的人数
分析：总的来说是一个判断一个图的连通分量的个数，用图的遍历解决，深度优先遍历。
1.因为给的是字母，要用两个map把它们转换成数字，从1开始排列命名所有不同的人的id，存储在两个map里面，一个字符串对应id，一个id对应字符串，方便查找，正好顺便统计了总共的人数idNumber。
2.建立两个数组，weight和G，分别存储每条边的权值和每个结点的权值，因为这两个题目中都要求得后判断。
3.用传递引用的方法深度优先dfs，这样传入的参数在dfs后还能保存想要求得的值
4.遍历过一条边之后就把这条边的权值设为0（ G[u][v] = G[v][u] = 0;）防止出现回路遍历死循环

#include <iostream>
#include <map>
using namespace std;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> ans;
int idNumber = 1, k;
int stoifunc(string s) {
    if(stringToInt[s] == 0) {
        stringToInt[s] = idNumber;
        intToString[idNumber] = s;
        return idNumber++;
    } else {
        return stringToInt[s];
    }
}
int G[2010][2010], weight[2010];
bool vis[2010];
void dfs(int u, int &head, int &numMember, int &totalweight) {
    vis[u] = true;
    numMember++;
    if(weight[u] > weight[head])
        head = u;
    for(int v = 1; v < idNumber; v++) {
        if(G[u][v] > 0) {
            totalweight += G[u][v];
            G[u][v] = G[v][u] = 0;
            if(vis[v] == false)
                dfs(v, head, numMember, totalweight);
        }
    }
}
void dfsTrave() {
    for(int i = 1; i < idNumber; i++) {
        if(vis[i] == false) {
            int head = i, numMember = 0, totalweight = 0;
            dfs(i, head, numMember, totalweight);
            if(numMember > 2 && totalweight > k)
                ans[intToString[head]] = numMember;
        }
    }
}
int main() {
    int n, w;
    cin >> n >> k;
    string s1, s2;
    for(int i = 0; i < n; i++) {
        cin >> s1 >> s2 >> w;
        int id1 = stoifunc(s1);
        int id2 = stoifunc(s2);
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }
    dfsTrave();
    cout << ans.size() << endl;
    for(auto it = ans.begin(); it != ans.end(); it++)
        cout << it->first << " " << it->second << endl;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

map<string, int> stringToInt;

map<int, string> intToString;

map<string, int> ans;

int idNumber = 1, k;

int stoifunc(string s) {

if(stringToInt[s] == 0) {

stringToInt[s] = idNumber;

intToString[idNumber] = s;

return idNumber++;

} else {

return stringToInt[s];

}

int G[2010][2010], weight[2010];

bool vis[2010];

void dfs(int u, int &head, int &numMember, int &totalweight) {

vis[u] = true;

numMember++;

if(weight[u] > weight[head])

head = u;

for(int v = 1; v < idNumber; v++) {

if(G[u][v] > 0) {

totalweight += G[u][v];

G[u][v] = G[v][u] = 0;

if(vis[v] == false)

dfs(v, head, numMember, totalweight);

}

void dfsTrave() {

for(int i = 1; i < idNumber; i++) {

if(vis[i] == false) {

int head = i, numMember = 0, totalweight = 0;

dfs(i, head, numMember, totalweight);

if(numMember > 2 && totalweight > k)

ans[intToString[head]] = numMember;

}

int main() {

int n, w;

cin >> n >> k;

string s1, s2;

for(int i = 0; i < n; i++) {

cin >> s1 >> s2 >> w;

int id1 = stoifunc(s1);

int id2 = stoifunc(s2);

weight[id1] += w;

weight[id2] += w;

G[id1][id2] += w;

G[id2][id1] += w;

}

dfsTrave();

cout << ans.size() << endl;

for(auto it = ans.begin(); it != ans.end(); it++)

cout << it->first << " " << it->second << endl;

return 0;

}

1024. Palindromic Number (25)-PAT甲级真题（大整数相加）

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 10^10) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:
67 3
Sample Output 1:
484
2
Sample Input 2:
69 3
Sample Output 2:
1353
3
题目大意：给定一个数字，和允许翻转后相加的次数cnt，求要多少次才能变成一个回文数字，输出那个回文数字和翻转相加了多少次，如果本身就是回文数字就输出0次，如果超过给定的次数cnt了，就输出那个不是回文的结果，并且输出给定的次数cnt
分析：1、会超出long int类型（会有两个点溢出错误），所以用字符串存储，大整数相加
2、可以通过对字符串翻转后比较来判断是否为回文串

#include <iostream>
#include <algorithm>
using namespace std;
string s;
void add(string t) {
    int len = s.length(), carry = 0;
    for(int i = 0; i < len; i++) {
        s[i] = s[i] + t[i] + carry - '0';
        carry = 0;
        if(s[i] > '9') {
            s[i] = s[i] - 10;
            carry = 1;
        }
    }
    if(carry) s += '1';
    reverse(s.begin(), s.end());
}
int main() {
    int cnt, i;
    cin >> s >> cnt;
    for(i = 0; i <= cnt; i++) {
        string t = s;
        reverse(t.begin(), t.end());
        if(s == t || i == cnt) break;
        add(t);
    }
    cout << s << endl << i;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

string s;

void add(string t) {

int len = s.length(), carry = 0;

for(int i = 0; i < len; i++) {

s[i] = s[i] + t[i] + carry - '0';

carry = 0;

if(s[i] > '9') {

s[i] = s[i] - 10;

carry = 1;

}

if(carry) s += '1';

reverse(s.begin(), s.end());

}

int main() {

int cnt, i;

cin >> s >> cnt;

for(i = 0; i <= cnt; i++) {

string t = s;

reverse(t.begin(), t.end());

if(s == t || i == cnt) break;

add(t);

}

cout << s << endl << i;

return 0;

}

L3-001. 凑零钱-PAT团体程序设计天梯赛GPLT（01背包，动态规划）

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数：N（<=104）是硬币的总个数，M（<=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 V1 <= V2 <= … <= Vk，满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。

注：我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”，是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

输入样例1：
8 9
5 9 8 7 2 3 4 1
输出样例1：
1 3 5
输入样例2：
4 8
7 2 4 3
输出样例2：
No Solution

分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010];
int w[10010];
bool choice[10010][10010];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010];

int w[10010];

bool choice[10010][10010];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i++)

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

1068. Find More Coins (30)-PAT甲级真题（01背包）

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution
题目大意：用n个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool choice[10010][110];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010], w[10010];

bool choice[10010][110];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i++)

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

L3-008. 喊山-PAT团体程序设计天梯赛GPLT（广度优先搜索）

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（<=10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（<=10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
输出样例：
2
6
4
0

分析：用二维数组，结点push_back的方式存储，因为每次都从1遍历到n会超时，而只要遍历到v[top].size()就不会超时。
用广度优先搜索，level记录当前结点的层数，level为自己的上一层结点的level+1，遇到更大层数的时候就令ans又为最大值，让ans取当层的最小值（在不等于被搜索结点本身的时候）。book记录当前结点有没有被访问过，如果没有被访问过就压入队列中，因为可能重复然后导致无限循环，无法输出～

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v(10010);
int book[10010];
int main() {
    int n, m, k, a, b;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 0; i < k; i++) {
        scanf("%d", &a);
        queue<int> q;
        fill(book, book + 10010, 0);
        q.push(a);
        int level[10010];
        int ans = 10010, maxlevel = 0;
        book[a] = 1;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            if(level[top] > maxlevel) {
                maxlevel = level[top];
                ans = 10010;
            }
            if(top != a)
                ans = min(ans, top);
            for(int j = 0; j < v[top].size(); j++) {
                if(book[v[top][j]] == 0) {
                    q.push(v[top][j]);
                    book[v[top][j]] = 1;
                    level[v[top][j]] = level[top] + 1;
                }
            }
        }
        if(ans != 10010) printf("%d\n", ans);
        else printf("0\n");
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

vector<vector<int>> v(10010);

int book[10010];

int main() {

int n, m, k, a, b;

scanf("%d%d%d", &n, &m, &k);

for(int i = 0; i < m; i++) {

scanf("%d%d", &a, &b);

v[a].push_back(b);

v[b].push_back(a);

}

for(int i = 0; i < k; i++) {

scanf("%d", &a);

queue<int> q;

fill(book, book + 10010, 0);

q.push(a);

int level[10010];

int ans = 10010, maxlevel = 0;

book[a] = 1;

while(!q.empty()) {

int top = q.front();

q.pop();

if(level[top] > maxlevel) {

maxlevel = level[top];

ans = 10010;

}

if(top != a)

ans = min(ans, top);

for(int j = 0; j < v[top].size(); j++) {

if(book[v[top][j]] == 0) {

q.push(v[top][j]);

book[v[top][j]] = 1;

level[v[top][j]] = level[top] + 1;

}

if(ans != 10010) printf("%d\n", ans);

else printf("0\n");

}

return 0;

}