Sensor Notification Propagation

In this problem, you are given a network of sensors connected by bidirectional paths. An initial sensor a is activated at time 0. Every minute, the notification propagates from a sensor to all of its adjacent sensors. However, a sensor will only forward the notification once (when it is first activated) even if there are multiple paths reaching it. Your task is to count the total number of notifications that are received exactly at time t.

Note: If a sensor can be reached via different independent paths at time t, each occurrence is counted.

The notification propagation follows a breadth-first search (BFS) pattern, but with a twist. When a sensor is reached at time t (exactly), it is counted immediately without marking it as visited. For times less than t, once a sensor is processed, it is marked as visited so that its neighbors are not enqueued more than once.

The problem can be mathematically interpreted as follows:

Given a graph \(G=(V,E)\) where \(V\) is the set of sensors and \(E\) is the set of bidirectional edges, let \(a \in V\) be the initial sensor activated at time 0. For each minute, notifications propagate along the edges. Count the total number of notifications that are delivered precisely at minute \(t\).

inputFormat

The input is given via stdin and has the following format:

n m a t
u1 v1
u2 v2
... 
um vm

Here:

• n is the number of sensors.
• m is the number of bidirectional paths.
• a is the 0-indexed identifier of the initially activated sensor.
• t is the time (in minutes) at which you want to count the notifications.
• Each of the next m lines contains two integers u and v indicating there is an edge between sensor u and sensor v.

outputFormat

Output a single integer to stdout which is the number of notifications received exactly at time \(t\).

## sample

5 4 0 3
0 1
0 2
1 3
3 4

1