## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 2576

# Reversing Arrows

By Dâmi Henrique, INATEL Brasil

Timelimit: 2

Bibi and Bibika are playing a simple game where the judge, with each round, makes a drawing with several circles and arrows linking some of them.

Bibi must count the least X number of arrows that need to be inverted to exist at least one path from A to B and Bibika must count the smallest amount Y of inverted arrows to exist at least one path in the opposite direction from B to A. The game who find the lowest value. If there is no path between A > B or B > A, the game ends in a draw, regardless of the number of arrows reversed.

As the judge in some rounds makes a very large drawing, it is quite complicated to check the veracity of the answers given by the girls. Your task is to automate this process for him.

## Input

The first line of each test case contains four integers C ( 1 ≤ C ≤ 104 ) , S ( 0 ≤ S ≤ 5 x 105), A e B, ( 1 ≤ A, B ≤ C ), where C is the number of circles, S is the number of arrows, A and B are the ends of the game. Each of the next S lines contain two integers C1 and C2, representing an arrow connecting the circle C1 to the circle C2.

## Output

For each test case, display the winner's name and the amount Q inverted arrows in Bibi format: Q or Bibika: Q. If the game ends in a draw, display Bibibibika.

 Input Samples Output Samples 6 7 1 5 1 2 1 6 3 2 4 2 4 6 5 4 5 3 Bibika: 1

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cstdio>
#include <deque>
#include <vector>
#define MAXN 10010
using namespace std;
typedef pair < int, int> ii;
vector<int> grafo[MAXN], transposto[MAXN];
int bibi, bibika;
int find(int x) {
if (x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (peso[x]  <  peso[y]) {
pai[x] = y;
} else if (peso[x] > peso[y]) {
pai[y] = x;
} else {
pai[x] = y;
peso[y]++;
}
}
int main() {
int c, s, a, b;
scanf("%d %d %d %d", &c, &s, &a, &b);
while (s--) {
int u, v;
scanf("%d %d", &u, &v);
join(u, v);
grafo[u].push_back(v);
transposto[v].push_back(u);
}
if (find(a) != find(b)) {
printf("Bibibibika\n");
return 0;
}
deque < ii> fila1, fila2;
fila1.push_back(ii(0, a));
while (!fila1.empty()) {
ii davez = fila1.front();
fila1.pop_front();
int v = davez.second, dist = davez.first;
if (v == b) {
bibi = dist;
break;
}
for (int u : grafo[v]) {
}
for (int u : transposto[v]) {
if (!processado1[u]) fila1.push_back(ii(dist + 1, u));
}
}
fila2.push_back(ii(0, b));
while (!fila2.empty()) {
ii davez = fila2.front();
fila2.pop_front();
int v = davez.second, dist = davez.first;
if (v == a) {
bibika = dist;
break;
}
for (int u : grafo[v]) {
}
for (int u : transposto[v]) {
if (!processado2[u]) fila2.push_back(ii(dist + 1, u));
}
}
if (bibi  <  bibika) {
printf("Bibi: %d\n", bibi);
} else if (bibi > bibika) {
printf("Bibika: %d\n", bibika);
} else {
printf("Bibibibika\n");
}
return 0;
}
``````
Copy The Code &

Input

cmd
6 7 1 5
1
1 6
3 2
4 2
4 6
5 4
5 3

Output

cmd
Bibika: 1