Breaking the Friend Chain

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Thanks to the growing influence of Facebook on our lives, people can be connected even if they think they're not. Even if someone is not your friend, it doesn't mean none of your friends has them as a friend, and their friends, and their friends' friends... The International Society of Unfriendliness and War has some connections between people to break. To do this, they will have to disable some Facebook accounts, as this will effectively ruin all the owner's connections, and disconnect their friendships.

To see how much effort is it to disconnect a given pair of people, they have hired you to find the minimum number of Facebook accounts they need to disable.

Input Specification

The first line is a pair of two numbers, N and M, where N, M \in \mathbb N; 2 \le N \le 10\,000 and M \le 20\,000, the number of people and the number of friendships, respectively. The next M lines are pairs of two integers, A and B, the id of the two people who are friends, where A, B \in \mathbb N; A, B \le N. You may assume no one can be friends with oneself. The next line will be two integers, X and Y, the two people to disconnect, following the same format as A and B.

The International Society of Unfriendliness and War has some bad news for you. The friends data were acquired illegally, so its quality is not guaranteed. In particular, if A is listed as with B's friend, there is a chance B will also be listed as A's friend, even though it is implied that this is the case.

Output Specification

Output the minimum number of Facebook accounts that need to be disabled to disconnect X and Y.

Sample Input 1

3 2
1 2
2 3
1 3

Sample Output 1


Explanation of Sample 1

There are three people and two friend relations: 1 is friends with 2, who is friends with 3. If we disable 2's Facebook account, 1 can no longer reach 3. There is no better way to ruin the link between 1 and 3. Therefore, we output 1 as we need to destroy a minimum of one Facebook account.

Sample Input 2

4 2
2 3
3 1
1 4

Sample Output 2


Explanation of Sample 2

There are no links between 1 and 4 in the first place, so no shady business needs to be done.


  • 9
    Epicnerdking  commented on Feb. 5, 2017, 9:13 p.m.

    "You may assume no one can be friends with oneself." Ouch.