Virus Containment in a Lab

Problem Statement

Virus Containment in a Lab Problem Description A high-security lab has N rooms, numbered 1 to N , joined by M two-way tunnels. A virus has been released in room S . Containment seals tunnels. A sealed tunnel can no longer be used in either direction. A room is isolated from S when no route of unsealed tunnels, however long, leads from that room to S . Seal as few tunnels as possible so that every room other than S is isolated from S , and report how many that takes. Two rooms may be joined by more than one tunnel, and each such tunnel is sealed separately. No tunnel joins a room to itself. Input Format Line 1: the integer N , the number of rooms. Line 2: the integer M , the number of tunnels. Line 3: the integer S , the infected room. Each of the next M lines: two integers u and v , a tunnel between rooms u and v . Output Format Print a single integer: the minimum number of tunnels that must be sealed. Examples Example 1 Input: 6 7 1 1 2 1 3 2 3 2 4 3 5 4 5 5 6 Output: 2 Only two tunne