Breaking the Friend Chain

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 64M

Author:

quantum

Problem type

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 it is 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$ ~N~ and $M$ ~M~, where $N, M \in \mathbb N; 2 \le N \le 10\,000$ and $M \le 20\,000$ ~M \le 20\,000~, the number of people and the number of friendships, respectively. The next $M$ ~M~ lines are pairs of two integers, $A$ ~A~ and $B$ ~B~, the id of the two people who are friends, where $A, B \in \mathbb N; A, B \le N$ ~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$ ~X~ and $Y$ ~Y~, the two people to disconnect, following the same format as $A$ ~A~ and $B$ ~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$ ~A~ is listed as $B$ ~B~'s friend, there is a chance $B$ ~B~ will also be listed as $A$ ~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$ ~X~ and $Y$ ~Y~.

Sample Input 1

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

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.

Comments

0

b_nary commented on Nov. 8, 2023, 5:03 a.m.

idk why i didnt realize you can just disable X

3

OneYearOld commented on Jan. 10, 2021, 10:52 p.m. ← edited →

This problem is the graph theory variant of List Minimum (Easy) in the sense that it seems impossible until you think about it for long enough, and then it becomes much easier.

15

Epicnerdking commented on Feb. 6, 2017, 2:13 a.m.

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

0

VictorZhu commented on Oct. 15, 2022, 5:16 p.m.

Imagine not having friends ... 😭