We were all SYNners.

A client and a server must establish a connection before they can communicate. In real networks, this is done through carefully designed handshakes that tolerate message reordering.

Implement a minimal client–server connection protocol over a simulated network.

You are given a simulated message-passing network. Messages are never dropped or duplicated, but may arrive out of order.

Your task is to implement a deterministic connection handshake between a client and a server.

---

Message Format

Message {
  src, dst, payload
}

• src is the source of the Message.
• dst is the destination of the Message.
• payload is a string, which is either "SYN", "ACK", or "SYN-ACK".

---

Network API

net_send(message)
net_recv()

• This API is already provided (you do not need to implement it).
• net_send enqueues a message into the network.
• net_recv returns the next delivered message, or nullopt if none are available.
• Messages may be delivered out of order.

---

Classes to implement

Client {
    Client(id, server_id)
    connect()
    tick()
    connected()
}

Server {
    Server(id)
    tick()
    has_connection(client_id)
}

Client

• The constructor Client(id, server_id) takes in two integers id and server_id, which indicate the ids of the Client and Server, respectively.

• connect() initiates a connection attempt. Returns nothing.

• tick() is called repeatedly by the judge. Returns nothing.

• connected() returns true iff the client considers the connection established, else false.

Server

• The constructor Server(id) takes in one integer id, the server’s id.

• tick() is called repeatedly by the judge. Returns nothing.

• has_connection(client_id) returns true iff the server considers client_id connected, else false.

---

Protocol

The handshake protocol is:

1. Client → Server: "SYN"

2. Server → Client: "SYN-ACK"

3. Client → Server: "ACK"

The connection is considered established when:

• the client has received "SYN-ACK" and sent "ACK", and

• the server has received "ACK" from that client.

---

tick semantics

The judge runs the simulation in discrete steps called ticks.

In each tick:

1. Zero or more messages may already be available via net_recv() (possibly out of order).

2. The judge calls client.tick() and server.tick() (order is unspecified).

3. Any messages the client/server choose to send must be sent using net_send() during their tick() call.

Your tick() must:

• repeatedly call net_recv() until it returns nullopt,

• process any messages that are addressed to that participant (msg.dst == my_id),

• update internal protocol state accordingly,

• send any required protocol messages using net_send().

Your tick() must not:

• block or wait for future messages,

• use real sockets or sleeping,

• assume messages arrive in order.

Progress happens across multiple calls to tick().

---

Behavioral Requirements

Client rules

• connect() must send exactly one "SYN" message to the server (and do nothing else).

• After connect() is called, the client must eventually send "ACK" only after it receives a valid "SYN-ACK" from the server.

• connected() must return true only after the client has sent its "ACK" (in response to "SYN-ACK").

Server rules

• Upon receiving "SYN" from a client c, the server must send "SYN-ACK" back to c.

• The server must mark client c as connected only after receiving "ACK" from c.

• has_connection(c) must return true iff client c has been marked connected.

---

Out-of-Order and Unexpected Messages

Messages can arrive out of order. Your implementation must be safe under any delivery order.

• If the server receives "ACK" from client c before it has ever received "SYN" from c, it must ignore that "ACK".

• If the client receives "SYN-ACK" before it has called connect(), it must ignore that message.

• Any message with an unknown payload, wrong destination, or invalid context must be ignored.

---

Determinism

For the same sequence of delivered messages, your implementation must behave deterministically.

There is no randomness in this problem, and no timeouts/retransmissions.

---

Input / Output Format

The judge will compile and run your Client and Server implementation in a hidden harness.

Therefore, you do not need to write any custom input/output parsing.

---

Notes

• You may not use OS networking APIs (no real sockets).

• You must implement the protocol logic and state transitions yourself.

• The goal is to correctly handle message ordering and connection state.