Problem Description

Design and implement a SatelliteNetwork class to simulate message propagation across an undirected graph of satellites. The class must provide the following methods:

Core Methods

• satellite_connected(satellite_id): Registers a new satellite with the given satellite_id. If a satellite with this ID already exists, an ErrDuplicateSatelliteId(satellite_id) error should be raised.
• relationship_established(satellite_id1, satellite_id2): Establishes a bidirectional communication link between satellite_id1 and satellite_id2. If either satellite_id1 or satellite_id2 does not exist, an ErrInvalidSatelliteId(offending_id) error should be raised, where offending_id is the invalid ID.
• message_received(satellite_ids): Simulates Earth sending the same message simultaneously at time t=0 to all satellites listed in satellite_ids. If any ID in the list does not exist, an ErrInvalidSatelliteId(offending_id) error should be raised.

Message Propagation Rules

1. First Reception: When a satellite first receives a message at time t, it attempts to forward it to each of its directly connected neighbors that have not yet received this specific message.
2. Forwarding Time: Each such neighbor receives the message at time t + 10s. Forwarding takes 10 seconds per sender.
3. Ignoring Subsequent Receptions: A satellite processes only its first reception of a given message and ignores any subsequent receptions of the same message.
4. Reporting Eligibility: A satellite becomes eligible to report back to Earth once all of its direct neighbors have received the message (from any sender).
5. Report Delivery Time: The satellite's report is delivered at the earliest time this eligibility condition becomes true, plus an additional 30 seconds.
6. Deterministic Report Order: When multiple reports are delivered at the exact same time, they must be processed in increasing SatelliteId order.

Side Effects and Output

• For each satellite report, the OnSatelliteReportedBack(satelliteId) callback must be invoked.
• These callbacks must be invoked in the exact chronological order of report delivery for that specific message.
• The methods themselves should not return or print anything else.

Assumptions and Constraints

• Satellite IDs are integers.
• Multiple calls to message_received should be treated as independent simulation runs; the state of the network (satellites and links) persists, but message propagation state resets for each new message.
• The design must handle a large number of N satellites and M links efficiently.
• All operations, especially report ordering, must ensure deterministic behavior.
• Candidates should provide code or pseudocode and analyze the time and space complexity of their solution.