Reconstruct DNA from tagged fragments

You are given a list of DNA fragments. Each fragment is represented by a Sequence object containing two endpoint labels and a DNA string payload.

Your task is to implement:

String shotgunSequence(List<Sequence> sequences)

The function must order the fragments into a single chain that uses every fragment exactly once, then return the reconstructed DNA string by concatenating the payload strings in that chain order.

Part 1 (Directed chaining)

Each fragment has:

• startId (string)
• endId (string)
• payload (string)

A fragment i can be followed by fragment j iff:

• i.endId == j.startId

Guarantees

• All labels ( startId / endId ) are unique identifiers where applicable.
• There exists exactly one valid ordering that uses all fragments.
• The valid ordering forms one continuous chain.

Example

Fragments:

• ( "AAA" , "AAC" , "AAAA" )
• ( "AGG" , "ACC" , "GGGG" )
• ( "AAC" , "ACT" , "TTTT" )
• ( "ACT" , "AGG" , "CCCC" )

Valid label chain: AAA → AAC → ACT → AGG → ACC

Output: "AAAATTTTCCCCGGGG"

Follow-up (Unknown direction / two tags)

Now each fragment has:

• tag1 (string)
• tag2 (string)
• payload (string)

Fragment orientation is unknown: a fragment can be traversed as either tag1 → tag2 or tag2 → tag1.

Two consecutive fragments can be connected if they share a tag (i.e., the end tag of the current traversal equals a tag on the next fragment, choosing its traversal direction appropriately).

Guarantees

• At least one valid ordering exists that uses all fragments exactly once.
• You must still use all fragments.

Example

Fragments:

• ( A , B , "AAAA" )
• ( B , C , "TTTT" )
• ( C , D , "CCCC" )
• ( D , B , "GGGG" )

One valid tag walk: A → B → C → D → B

Output: "AAAATTTTCCCCGGGG"

What to return

Return the concatenation of payloads in the chosen fragment order. (No extra separators; do not merge/overlap payload strings.)