Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2023. december 3.

December 3, 2023, 10:00 AM – December 3, 2023, 3:30 PM

Firewall

Encrypting our data is only one side of a coin, since it is worthless if an attacker is able to intrude our systems and potentially delete all our data. This it is mandatory to apply firewalls to restrict our systems and it is also equally important that in the case of attack we must be able to respond immediately. Our task as a cybersecurity expert is none less than to deploy a firewall onto an virus-infected system to minimize the damage. We are equipped with the following knowledge:

  • The network is made up of routers (nodes) which are connected to each other (edges). The nodes are labeled by unique positive integers.
  • The virus can enter at any node in our network, but always strictly at one router. We know this entry point.
  • The virus is able to infect other routers through the direct connections between them, so it can reach any router which is directly connected to an infected one.
  • The virus is not able to infect the router where we deployed a firewall.
  • The attack happens "instantly", so we only have time to deploy one firewall.
  • The entry point is "already lost", so we cannot deploy a firewall there.
Our task is that if we are given a network infrastructure and an entry point deploy a firewall to the router which is able to protect the most routers (so that the virus can infect the least amount of routers). If there are multiple routers like this, then output the smallest label.

Input

The input consists of four units:

  • The first line is a single integer n which is the number of routers.
  • The second line is a single integer e which is the entry point of the virus.
  • The third line is a single integer m which is the number of edges.
  • Each of the next m lines contain two numbers separated by a single space character which gives us the edges (for example 2 5 means that router number 2 and 5 are connected).

Output

The output is a single integer which based on the above tells us where to deploy a firewall such that after the virus finishes its rampage the amount of infected routers if the lowest. The router where we deploy the firewall is considered "clean", so we can always protect at least one router. If there are multiple possibilities, then output the smallest number.

Restrictions

  • n is at most 500
  • m is at most 800
  • the routers are numbered consecutively: 0,1,2,...,n-1
  • there can be disjunct, not connecter router-groups. The virus cannot travel between these groups
  • the exercise is well-defined, so the edges connect existing routers, there can only be a maximum of 1 edge between two routers and the edges are undirected (the virus can travel both ways)

Example

Input:
  1. 8
  2. 0
  3. 7
  4. 0 1
  5. 1 2
  6. 2 3
  7. 0 4
  8. 4 5
  9. 5 6
  10. 6 7
download as text file Output:
  1. 4
download as text file

Explanation

  1. 0-1-2-3
  2.  \
  3.   [4]-ok(5)-ok(6)-ok(7)
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024